492ea9ea62bb69bf980a8ededa1de2221c64ea80
1 # Copyright 2014 MINES ParisTech
3 # This file is part of LinPy.
5 # LinPy is free software: you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License as published by
7 # the Free Software Foundation, either version 3 of the License, or
8 # (at your option) any later version.
10 # LinPy is distributed in the hope that it will be useful,
11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 # GNU General Public License for more details.
15 # You should have received a copy of the GNU General Public License
16 # along with LinPy. If not, see <http://www.gnu.org/licenses/>.
23 from collections
import OrderedDict
, defaultdict
, Mapping
24 from fractions
import Fraction
, gcd
29 'Symbol', 'Dummy', 'symbols',
34 def _polymorphic(func
):
35 @functools.wraps(func
)
36 def wrapper(left
, right
):
37 if isinstance(right
, LinExpr
):
38 return func(left
, right
)
39 elif isinstance(right
, numbers
.Rational
):
40 right
= Rational(right
)
41 return func(left
, right
)
48 A linear expression consists of a list of coefficient-variable pairs
49 that capture the linear terms, plus a constant term. Linear expressions
50 are used to build constraints. They are temporary objects that typically
53 Linear expressions are generally built using overloaded operators. For
54 example, if x is a Symbol, then x + 1 is an instance of LinExpr.
56 LinExpr instances are hashable, and should be treated as immutable.
59 def __new__(cls
, coefficients
=None, constant
=0):
61 Return a linear expression from a dictionary or a sequence, that maps
62 symbols to their coefficients, and a constant term. The coefficients and
63 the constant term must be rational numbers.
65 For example, the linear expression x + 2y + 1 can be constructed using
66 one of the following instructions:
68 >>> x, y = symbols('x y')
69 >>> LinExpr({x: 1, y: 2}, 1)
70 >>> LinExpr([(x, 1), (y, 2)], 1)
72 However, it may be easier to use overloaded operators:
74 >>> x, y = symbols('x y')
77 Alternatively, linear expressions can be constructed from a string:
79 >>> LinExpr('x + 2*y + 1')
81 A linear expression with a single symbol of coefficient 1 and no
82 constant term is automatically subclassed as a Symbol instance. A linear
83 expression with no symbol, only a constant term, is automatically
84 subclassed as a Rational instance.
86 if isinstance(coefficients
, str):
88 raise TypeError('too many arguments')
89 return LinExpr
.fromstring(coefficients
)
90 if coefficients
is None:
91 return Rational(constant
)
92 if isinstance(coefficients
, Mapping
):
93 coefficients
= coefficients
.items()
94 coefficients
= list(coefficients
)
95 for symbol
, coefficient
in coefficients
:
96 if not isinstance(symbol
, Symbol
):
97 raise TypeError('symbols must be Symbol instances')
98 if not isinstance(coefficient
, numbers
.Rational
):
99 raise TypeError('coefficients must be rational numbers')
100 if not isinstance(constant
, numbers
.Rational
):
101 raise TypeError('constant must be a rational number')
102 if len(coefficients
) == 0:
103 return Rational(constant
)
104 if len(coefficients
) == 1 and constant
== 0:
105 symbol
, coefficient
= coefficients
[0]
108 coefficients
= [(symbol
, Fraction(coefficient
))
109 for symbol
, coefficient
in coefficients
if coefficient
!= 0]
110 coefficients
.sort(key
=lambda item
: item
[0].sortkey())
111 self
= object().__new
__(cls
)
112 self
._coefficients
= OrderedDict(coefficients
)
113 self
._constant
= Fraction(constant
)
114 self
._symbols
= tuple(self
._coefficients
)
115 self
._dimension
= len(self
._symbols
)
118 def coefficient(self
, symbol
):
120 Return the coefficient value of the given symbol, or 0 if the symbol
121 does not appear in the expression.
123 if not isinstance(symbol
, Symbol
):
124 raise TypeError('symbol must be a Symbol instance')
125 return self
._coefficients
.get(symbol
, Fraction(0))
127 __getitem__
= coefficient
129 def coefficients(self
):
131 Iterate over the pairs (symbol, value) of linear terms in the
132 expression. The constant term is ignored.
134 yield from self
._coefficients
.items()
139 The constant term of the expression.
141 return self
._constant
146 The tuple of symbols present in the expression, sorted according to
154 The dimension of the expression, i.e. the number of symbols present in
157 return self
._dimension
160 return hash((tuple(self
._coefficients
.items()), self
._constant
))
162 def isconstant(self
):
164 Return True if the expression only consists of a constant term. In this
165 case, it is a Rational instance.
171 Return True if an expression only consists of a symbol with coefficient
172 1. In this case, it is a Symbol instance.
178 Iterate over the coefficient values in the expression, and the constant
181 yield from self
._coefficients
.values()
194 def __add__(self
, other
):
196 Return the sum of two linear expressions.
198 coefficients
= defaultdict(Fraction
, self
._coefficients
)
199 for symbol
, coefficient
in other
._coefficients
.items():
200 coefficients
[symbol
] += coefficient
201 constant
= self
._constant
+ other
._constant
202 return LinExpr(coefficients
, constant
)
207 def __sub__(self
, other
):
209 Return the difference between two linear expressions.
211 coefficients
= defaultdict(Fraction
, self
._coefficients
)
212 for symbol
, coefficient
in other
._coefficients
.items():
213 coefficients
[symbol
] -= coefficient
214 constant
= self
._constant
- other
._constant
215 return LinExpr(coefficients
, constant
)
218 def __rsub__(self
, other
):
221 def __mul__(self
, other
):
223 Return the product of the linear expression by a rational.
225 if isinstance(other
, numbers
.Rational
):
226 coefficients
= ((symbol
, coefficient
* other
)
227 for symbol
, coefficient
in self
._coefficients
.items())
228 constant
= self
._constant
* other
229 return LinExpr(coefficients
, constant
)
230 return NotImplemented
234 def __truediv__(self
, other
):
236 Return the quotient of the linear expression by a rational.
238 if isinstance(other
, numbers
.Rational
):
239 coefficients
= ((symbol
, coefficient
/ other
)
240 for symbol
, coefficient
in self
._coefficients
.items())
241 constant
= self
._constant
/ other
242 return LinExpr(coefficients
, constant
)
243 return NotImplemented
246 def __eq__(self
, other
):
248 Test whether two linear expressions are equal.
250 return isinstance(other
, LinExpr
) and \
251 self
._coefficients
== other
._coefficients
and \
252 self
._constant
== other
._constant
254 def __le__(self
, other
):
255 from .polyhedra
import Le
256 return Le(self
, other
)
258 def __lt__(self
, other
):
259 from .polyhedra
import Lt
260 return Lt(self
, other
)
262 def __ge__(self
, other
):
263 from .polyhedra
import Ge
264 return Ge(self
, other
)
266 def __gt__(self
, other
):
267 from .polyhedra
import Gt
268 return Gt(self
, other
)
272 Return the expression multiplied by its lowest common denominator to
273 make all values integer.
275 lcm
= functools
.reduce(lambda a
, b
: a
*b
// gcd(a
, b
),
276 [value
.denominator
for value
in self
.values()])
279 def subs(self
, symbol
, expression
=None):
281 Substitute the given symbol by an expression and return the resulting
282 expression. Raise TypeError if the resulting expression is not linear.
284 >>> x, y = symbols('x y')
289 To perform multiple substitutions at once, pass a sequence or a
290 dictionary of (old, new) pairs to subs.
292 >>> e.subs({x: y, y: x})
295 if expression
is None:
296 if isinstance(symbol
, Mapping
):
297 symbol
= symbol
.items()
298 substitutions
= symbol
300 substitutions
= [(symbol
, expression
)]
302 for symbol
, expression
in substitutions
:
303 if not isinstance(symbol
, Symbol
):
304 raise TypeError('symbols must be Symbol instances')
305 coefficients
= [(othersymbol
, coefficient
)
306 for othersymbol
, coefficient
in result
._coefficients
.items()
307 if othersymbol
!= symbol
]
308 coefficient
= result
._coefficients
.get(symbol
, 0)
309 constant
= result
._constant
310 result
= LinExpr(coefficients
, constant
) + coefficient
*expression
314 def _fromast(cls
, node
):
315 if isinstance(node
, ast
.Module
) and len(node
.body
) == 1:
316 return cls
._fromast
(node
.body
[0])
317 elif isinstance(node
, ast
.Expr
):
318 return cls
._fromast
(node
.value
)
319 elif isinstance(node
, ast
.Name
):
320 return Symbol(node
.id)
321 elif isinstance(node
, ast
.Num
):
322 return Rational(node
.n
)
323 elif isinstance(node
, ast
.UnaryOp
) and isinstance(node
.op
, ast
.USub
):
324 return -cls
._fromast
(node
.operand
)
325 elif isinstance(node
, ast
.BinOp
):
326 left
= cls
._fromast
(node
.left
)
327 right
= cls
._fromast
(node
.right
)
328 if isinstance(node
.op
, ast
.Add
):
330 elif isinstance(node
.op
, ast
.Sub
):
332 elif isinstance(node
.op
, ast
.Mult
):
334 elif isinstance(node
.op
, ast
.Div
):
336 raise SyntaxError('invalid syntax')
338 _RE_NUM_VAR
= re
.compile(r
'(\d+|\))\s*([^\W\d_]\w*|\()')
341 def fromstring(cls
, string
):
343 Create an expression from a string. Raise SyntaxError if the string is
344 not properly formatted.
346 # add implicit multiplication operators, e.g. '5x' -> '5*x'
347 string
= LinExpr
._RE
_NUM
_VAR
.sub(r
'\1*\2', string
)
348 tree
= ast
.parse(string
, 'eval')
349 expr
= cls
._fromast
(tree
)
350 if not isinstance(expr
, cls
):
351 raise SyntaxError('invalid syntax')
356 for i
, (symbol
, coefficient
) in enumerate(self
.coefficients()):
360 elif coefficient
== -1:
361 string
+= '-' if i
== 0 else ' - '
363 string
+= '{}*'.format(coefficient
)
364 elif coefficient
> 0:
365 string
+= ' + {}*'.format(coefficient
)
367 string
+= ' - {}*'.format(-coefficient
)
368 string
+= '{}'.format(symbol
)
369 constant
= self
.constant
371 string
+= '{}'.format(constant
)
373 string
+= ' + {}'.format(constant
)
375 string
+= ' - {}'.format(-constant
)
378 def _repr_latex_(self
):
380 for i
, (symbol
, coefficient
) in enumerate(self
.coefficients()):
384 elif coefficient
== -1:
385 string
+= '-' if i
== 0 else ' - '
387 string
+= '{}'.format(coefficient
._repr
_latex
_().strip('$'))
388 elif coefficient
> 0:
389 string
+= ' + {}'.format(coefficient
._repr
_latex
_().strip('$'))
390 elif coefficient
< 0:
391 string
+= ' - {}'.format((-coefficient
)._repr
_latex
_().strip('$'))
392 string
+= '{}'.format(symbol
._repr
_latex
_().strip('$'))
393 constant
= self
.constant
395 string
+= '{}'.format(constant
._repr
_latex
_().strip('$'))
397 string
+= ' + {}'.format(constant
._repr
_latex
_().strip('$'))
399 string
+= ' - {}'.format((-constant
)._repr
_latex
_().strip('$'))
400 return '$${}$$'.format(string
)
402 def _parenstr(self
, always
=False):
404 if not always
and (self
.isconstant() or self
.issymbol()):
407 return '({})'.format(string
)
410 def fromsympy(cls
, expr
):
412 Create a linear expression from a sympy expression. Raise TypeError is
413 the sympy expression is not linear.
418 for symbol
, coefficient
in expr
.as_coefficients_dict().items():
419 coefficient
= Fraction(coefficient
.p
, coefficient
.q
)
420 if symbol
== sympy
.S
.One
:
421 constant
= coefficient
422 elif isinstance(symbol
, sympy
.Dummy
):
423 # we cannot properly convert dummy symbols
424 raise TypeError('cannot convert dummy symbols')
425 elif isinstance(symbol
, sympy
.Symbol
):
426 symbol
= Symbol(symbol
.name
)
427 coefficients
.append((symbol
, coefficient
))
429 raise TypeError('non-linear expression: {!r}'.format(expr
))
430 expr
= LinExpr(coefficients
, constant
)
431 if not isinstance(expr
, cls
):
432 raise TypeError('cannot convert to a {} instance'.format(cls
.__name
__))
437 Convert the linear expression to a sympy expression.
441 for symbol
, coefficient
in self
.coefficients():
442 term
= coefficient
* sympy
.Symbol(symbol
.name
)
444 expr
+= self
.constant
448 class Symbol(LinExpr
):
450 Symbols are the basic components to build expressions and constraints.
451 They correspond to mathematical variables. Symbols are instances of
452 class LinExpr and inherit its functionalities.
454 Two instances of Symbol are equal if they have the same name.
457 def __new__(cls
, name
):
459 Return a symbol with the name string given in argument.
461 if not isinstance(name
, str):
462 raise TypeError('name must be a string')
463 node
= ast
.parse(name
)
465 name
= node
.body
[0].value
.id
466 except (AttributeError, SyntaxError):
467 raise SyntaxError('invalid syntax')
468 self
= object().__new
__(cls
)
470 self
._coefficients
= {self
: Fraction(1)}
471 self
._constant
= Fraction(0)
472 self
._symbols
= (self
,)
479 The name of the symbol.
484 return hash(self
.sortkey())
488 Return a sorting key for the symbol. It is useful to sort a list of
489 symbols in a consistent order, as comparison functions are overridden
490 (see the documentation of class LinExpr).
492 >>> sort(symbols, key=Symbol.sortkey)
499 def __eq__(self
, other
):
500 return self
.sortkey() == other
.sortkey()
504 Return a new Dummy symbol instance with the same name.
506 return Dummy(self
.name
)
511 def _repr_latex_(self
):
512 return '$${}$$'.format(self
.name
)
517 This function returns a tuple of symbols whose names are taken from a comma
518 or whitespace delimited string, or a sequence of strings. It is useful to
519 define several symbols at once.
521 >>> x, y = symbols('x y')
522 >>> x, y = symbols('x, y')
523 >>> x, y = symbols(['x', 'y'])
525 if isinstance(names
, str):
526 names
= names
.replace(',', ' ').split()
527 return tuple(Symbol(name
) for name
in names
)
532 A variation of Symbol in which all symbols are unique and identified by
533 an internal count index. If a name is not supplied then a string value
534 of the count index will be used. This is useful when a unique, temporary
535 variable is needed and the name of the variable used in the expression
538 Unlike Symbol, Dummy instances with the same name are not equal:
541 >>> x1, x2 = Dummy('x'), Dummy('x')
552 def __new__(cls
, name
=None):
554 Return a fresh dummy symbol with the name string given in argument.
557 name
= 'Dummy_{}'.format(Dummy
._count
)
558 elif not isinstance(name
, str):
559 raise TypeError('name must be a string')
560 self
= object().__new
__(cls
)
561 self
._index
= Dummy
._count
562 self
._name
= name
.strip()
563 self
._coefficients
= {self
: Fraction(1)}
564 self
._constant
= Fraction(0)
565 self
._symbols
= (self
,)
571 return hash(self
.sortkey())
574 return self
._name
, self
._index
577 return '_{}'.format(self
.name
)
579 def _repr_latex_(self
):
580 return '$${}_{{{}}}$$'.format(self
.name
, self
._index
)
583 class Rational(LinExpr
, Fraction
):
585 A particular case of linear expressions are rational values, i.e. linear
586 expressions consisting only of a constant term, with no symbol. They are
587 implemented by the Rational class, that inherits from both LinExpr and
588 fractions.Fraction classes.
591 def __new__(cls
, numerator
=0, denominator
=None):
592 self
= object().__new
__(cls
)
593 self
._coefficients
= {}
594 self
._constant
= Fraction(numerator
, denominator
)
597 self
._numerator
= self
._constant
.numerator
598 self
._denominator
= self
._constant
.denominator
602 return Fraction
.__hash
__(self
)
608 def isconstant(self
):
612 return Fraction
.__bool
__(self
)
615 if self
.denominator
== 1:
616 return '{!r}'.format(self
.numerator
)
618 return '{!r}/{!r}'.format(self
.numerator
, self
.denominator
)
620 def _repr_latex_(self
):
621 if self
.denominator
== 1:
622 return '$${}$$'.format(self
.numerator
)
623 elif self
.numerator
< 0:
624 return '$$-\\frac{{{}}}{{{}}}$$'.format(-self
.numerator
,
627 return '$$\\frac{{{}}}{{{}}}$$'.format(self
.numerator
,