Centralize version information
[linpy.git] / doc / reference.rst
1
2 .. _reference:
3
4 Module Reference
5 ================
6
7
8 .. _reference_symbols:
9
10 Symbols
11 -------
12
13 *Symbols* are the basic components to build expressions and constraints.
14 They correspond to mathematical variables.
15
16 .. class:: Symbol(name)
17
18 Return a symbol with the name string given in argument.
19 Alternatively, the function :func:`symbols` allows to create several symbols at once.
20 Symbols are instances of class :class:`LinExpr` and inherit its functionalities.
21
22 >>> x = Symbol('x')
23 >>> x
24 x
25
26 Two instances of :class:`Symbol` are equal if they have the same name.
27
28 .. attribute:: name
29
30 The name of the symbol.
31
32 .. method:: asdummy()
33
34 Return a new :class:`Dummy` symbol instance with the same name.
35
36 .. method:: sortkey()
37
38 Return a sorting key for the symbol.
39 It is useful to sort a list of symbols in a consistent order, as comparison functions are overridden (see the documentation of class :class:`LinExpr`).
40
41 >>> sort(symbols, key=Symbol.sortkey)
42
43
44 .. function:: symbols(names)
45
46 This function returns a tuple of symbols whose names are taken from a comma or whitespace delimited string, or a sequence of strings.
47 It is useful to define several symbols at once.
48
49 >>> x, y = symbols('x y')
50 >>> x, y = symbols('x, y')
51 >>> x, y = symbols(['x', 'y'])
52
53
54 Sometimes you need to have a unique symbol. For example, you might need a temporary one in some calculation, which is going to be substituted for something else at the end anyway.
55 This is achieved using ``Dummy('x')``.
56
57 .. class:: Dummy(name=None)
58
59 A variation of :class:`Symbol` in which all symbols are unique and identified by an internal count index.
60 If a name is not supplied then a string value of the count index will be used.
61 This is useful when a unique, temporary variable is needed and the name of the variable used in the expression is not important.
62
63 Unlike :class:`Symbol`, :class:`Dummy` instances with the same name are not equal:
64
65 >>> x = Symbol('x')
66 >>> x1, x2 = Dummy('x'), Dummy('x')
67 >>> x == x1
68 False
69 >>> x1 == x2
70 False
71 >>> x1 == x1
72 True
73
74
75 .. _reference_linexprs:
76
77 Linear Expressions
78 ------------------
79
80 A *linear expression* consists of a list of coefficient-variable pairs that capture the linear terms, plus a constant term.
81 Linear expressions are used to build constraints. They are temporary objects that typically have short lifespans.
82
83 Linear expressions are generally built using overloaded operators.
84 For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :class:`LinExpr`.
85
86 .. class:: LinExpr(coefficients=None, constant=0)
87 LinExpr(string)
88
89 Return a linear expression from a dictionary or a sequence, that maps symbols to their coefficients, and a constant term.
90 The coefficients and the constant term must be rational numbers.
91
92 For example, the linear expression ``x + 2y + 1`` can be constructed using one of the following instructions:
93
94 >>> x, y = symbols('x y')
95 >>> LinExpr({x: 1, y: 2}, 1)
96 >>> LinExpr([(x, 1), (y, 2)], 1)
97
98 However, it may be easier to use overloaded operators:
99
100 >>> x, y = symbols('x y')
101 >>> x + 2*y + 1
102
103 Alternatively, linear expressions can be constructed from a string:
104
105 >>> LinExpr('x + 2*y + 1')
106
107 :class:`LinExpr` instances are hashable, and should be treated as immutable.
108
109 A linear expression with a single symbol of coefficient 1 and no constant term is automatically subclassed as a :class:`Symbol` instance.
110 A linear expression with no symbol, only a constant term, is automatically subclassed as a :class:`Rational` instance.
111
112 .. method:: coefficient(symbol)
113 __getitem__(symbol)
114
115 Return the coefficient value of the given symbol, or ``0`` if the symbol does not appear in the expression.
116
117 .. method:: coefficients()
118
119 Iterate over the pairs ``(symbol, value)`` of linear terms in the expression.
120 The constant term is ignored.
121
122 .. attribute:: constant
123
124 The constant term of the expression.
125
126 .. attribute:: symbols
127
128 The tuple of symbols present in the expression, sorted according to :meth:`Symbol.sortkey`.
129
130 .. attribute:: dimension
131
132 The dimension of the expression, i.e. the number of symbols present in it.
133
134 .. method:: isconstant()
135
136 Return ``True`` if the expression only consists of a constant term.
137 In this case, it is a :class:`Rational` instance.
138
139 .. method:: issymbol()
140
141 Return ``True`` if an expression only consists of a symbol with coefficient ``1``.
142 In this case, it is a :class:`Symbol` instance.
143
144 .. method:: values()
145
146 Iterate over the coefficient values in the expression, and the constant term.
147
148 .. method:: __add__(expr)
149
150 Return the sum of two linear expressions.
151
152 .. method:: __sub__(expr)
153
154 Return the difference between two linear expressions.
155
156 .. method:: __mul__(value)
157
158 Return the product of the linear expression by a rational.
159
160 .. method:: __truediv__(value)
161
162 Return the quotient of the linear expression by a rational.
163
164 .. method:: __eq__(expr)
165
166 Test whether two linear expressions are equal.
167
168 As explained below, it is possible to create polyhedra from linear expressions using comparison methods.
169
170 .. method:: __lt__(expr)
171 __le__(expr)
172 __ge__(expr)
173 __gt__(expr)
174
175 Create a new :class:`Polyhedron` instance whose unique constraint is the comparison between two linear expressions.
176 As an alternative, functions :func:`Lt`, :func:`Le`, :func:`Ge` and :func:`Gt` can be used.
177
178 >>> x, y = symbols('x y')
179 >>> x < y
180 Le(x - y + 1, 0)
181
182 .. method:: scaleint()
183
184 Return the expression multiplied by its lowest common denominator to make all values integer.
185
186 .. method:: subs(symbol, expression)
187 subs(pairs)
188
189 Substitute the given symbol by an expression and return the resulting expression.
190 Raise :exc:`TypeError` if the resulting expression is not linear.
191
192 >>> x, y = symbols('x y')
193 >>> e = x + 2*y + 1
194 >>> e.subs(y, x - 1)
195 3*x - 1
196
197 To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
198
199 >>> e.subs({x: y, y: x})
200 2*x + y + 1
201
202 .. classmethod:: fromstring(string)
203
204 Create an expression from a string.
205 Raise :exc:`SyntaxError` if the string is not properly formatted.
206
207 There are also methods to convert linear expressions to and from `SymPy <http://sympy.org>`_ expressions:
208
209 .. classmethod:: fromsympy(expr)
210
211 Create a linear expression from a :mod:`sympy` expression.
212 Raise :exc:`TypeError` is the :mod:`sympy` expression is not linear.
213
214 .. method:: tosympy()
215
216 Convert the linear expression to a sympy expression.
217
218
219 Apart from :mod:`Symbol`, a particular case of linear expressions are rational values, i.e. linear expressions consisting only of a constant term, with no symbol.
220 They are implemented by the :class:`Rational` class, that inherits from both :class:`LinExpr` and :class:`fractions.Fraction` classes.
221
222 .. class:: Rational(numerator, denominator=1)
223 Rational(string)
224
225 The first version requires that the *numerator* and *denominator* are instances of :class:`numbers.Rational` and returns a new :class:`Rational` instance with the value ``numerator/denominator``.
226 If the denominator is ``0``, it raises a :exc:`ZeroDivisionError`.
227 The other version of the constructor expects a string.
228 The usual form for this instance is::
229
230 [sign] numerator ['/' denominator]
231
232 where the optional ``sign`` may be either '+' or '-' and the ``numerator`` and ``denominator`` (if present) are strings of decimal digits.
233
234 See the documentation of :class:`fractions.Fraction` for more information and examples.
235
236
237 .. _reference_polyhedra:
238
239 Polyhedra
240 ---------
241
242 A *convex polyhedron* (or simply "polyhedron") is the space defined by a system of linear equalities and inequalities.
243 This space can be unbounded.
244
245 .. class:: Polyhedron(equalities, inequalities)
246 Polyhedron(string)
247 Polyhedron(geometric object)
248
249 Return a polyhedron from two sequences of linear expressions: *equalities* is a list of expressions equal to ``0``, and *inequalities* is a list of expressions greater or equal to ``0``.
250 For example, the polyhedron ``0 <= x <= 2, 0 <= y <= 2`` can be constructed with:
251
252 >>> x, y = symbols('x y')
253 >>> square = Polyhedron([], [x, 2 - x, y, 2 - y])
254
255 It may be easier to use comparison operators :meth:`LinExpr.__lt__`, :meth:`LinExpr.__le__`, :meth:`LinExpr.__ge__`, :meth:`LinExpr.__gt__`, or functions :func:`Lt`, :func:`Le`, :func:`Eq`, :func:`Ge` and :func:`Gt`, using one of the following instructions:
256
257 >>> x, y = symbols('x y')
258 >>> square = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2)
259 >>> square = Le(0, x, 2) & Le(0, y, 2)
260
261 It is also possible to build a polyhedron from a string.
262
263 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
264
265 Finally, a polyhedron can be constructed from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.aspolyedron` method.
266 This way, it is possible to compute the polyhedral hull of a :class:`Domain` instance, i.e., the convex hull of two polyhedra:
267
268 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
269 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
270 >>> Polyhedron(square | square2)
271
272 A polyhedron is a :class:`Domain` instance, and, therefore, inherits the functionalities of this class.
273 It is also a :class:`GeometricObject` instance.
274
275 .. attribute:: equalities
276
277 The tuple of equalities.
278 This is a list of :class:`LinExpr` instances that are equal to ``0`` in the polyhedron.
279
280 .. attribute:: inequalities
281
282 The tuple of inequalities.
283 This is a list of :class:`LinExpr` instances that are greater or equal to ``0`` in the polyhedron.
284
285 .. attribute:: constraints
286
287 The tuple of constraints, i.e., equalities and inequalities.
288 This is semantically equivalent to: ``equalities + inequalities``.
289
290 .. method:: convex_union(polyhedron[, ...])
291
292 Return the convex union of two or more polyhedra.
293
294 .. method:: asinequalities()
295
296 Express the polyhedron using inequalities, given as a list of expressions greater or equal to 0.
297
298 .. method:: widen(polyhedron)
299
300 Compute the *standard widening* of two polyhedra, à la Halbwachs.
301
302 In its current implementation, this method is slow and should not be used on large polyhedra.
303
304
305 .. data:: Empty
306
307 The empty polyhedron, whose set of constraints is not satisfiable.
308
309 .. data:: Universe
310
311 The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.
312
313
314 .. _reference_domains:
315
316 Domains
317 -------
318
319 A *domain* is a union of polyhedra.
320 Unlike polyhedra, domains allow exact computation of union, subtraction and complementary operations.
321
322 .. class:: Domain(*polyhedra)
323 Domain(string)
324 Domain(geometric object)
325
326 Return a domain from a sequence of polyhedra.
327
328 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
329 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
330 >>> dom = Domain([square, square2])
331
332 It is also possible to build domains from polyhedra using arithmetic operators :meth:`Domain.__and__`, :meth:`Domain.__or__` or functions :func:`And` and :func:`Or`, using one of the following instructions:
333
334 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
335 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
336 >>> dom = square | square2
337 >>> dom = Or(square, square2)
338
339 Alternatively, a domain can be built from a string:
340
341 >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 2 <= x <= 4, 2 <= y <= 4')
342
343 Finally, a domain can be built from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method.
344
345 A domain is also a :class:`GeometricObject` instance.
346 A domain with a unique polyhedron is automatically subclassed as a :class:`Polyhedron` instance.
347
348 .. attribute:: polyhedra
349
350 The tuple of polyhedra present in the domain.
351
352 .. attribute:: symbols
353
354 The tuple of symbols present in the domain equations, sorted according to :meth:`Symbol.sortkey`.
355
356 .. attribute:: dimension
357
358 The dimension of the domain, i.e. the number of symbols present in it.
359
360 .. method:: isempty()
361
362 Return ``True`` if the domain is empty, that is, equal to :data:`Empty`.
363
364 .. method:: __bool__()
365
366 Return ``True`` if the domain is non-empty.
367
368 .. method:: isuniverse()
369
370 Return ``True`` if the domain is universal, that is, equal to :data:`Universe`.
371
372 .. method:: isbounded()
373
374 Return ``True`` is the domain is bounded.
375
376 .. method:: __eq__(domain)
377
378 Return ``True`` if two domains are equal.
379
380 .. method:: isdisjoint(domain)
381
382 Return ``True`` if two domains have a null intersection.
383
384 .. method:: issubset(domain)
385 __le__(domain)
386
387 Report whether another domain contains the domain.
388
389 .. method:: __lt__(domain)
390
391 Report whether another domain is contained within the domain.
392
393 .. method:: complement()
394 __invert__()
395
396 Return the complementary domain of the domain.
397
398 .. method:: make_disjoint()
399
400 Return an equivalent domain, whose polyhedra are disjoint.
401
402 .. method:: coalesce()
403
404 Simplify the representation of the domain by trying to combine pairs of polyhedra into a single polyhedron, and return the resulting domain.
405
406 .. method:: detect_equalities()
407
408 Simplify the representation of the domain by detecting implicit equalities, and return the resulting domain.
409
410 .. method:: remove_redundancies()
411
412 Remove redundant constraints in the domain, and return the resulting domain.
413
414 .. method:: project(symbols)
415
416 Project out the sequence of symbols given in arguments, and return the resulting domain.
417
418 .. method:: sample()
419
420 Return a sample of the domain, as an integer instance of :class:`Point`.
421 If the domain is empty, a :exc:`ValueError` exception is raised.
422
423 .. method:: intersection(domain[, ...])
424 __and__(domain)
425
426 Return the intersection of two or more domains as a new domain.
427 As an alternative, function :func:`And` can be used.
428
429 .. method:: union(domain[, ...])
430 __or__(domain)
431 __add__(domain)
432
433 Return the union of two or more domains as a new domain.
434 As an alternative, function :func:`Or` can be used.
435
436 .. method:: difference(domain)
437 __sub__(domain)
438
439 Return the difference between two domains as a new domain.
440
441 .. method:: lexmin()
442
443 Return the lexicographic minimum of the elements in the domain.
444
445 .. method:: lexmax()
446
447 Return the lexicographic maximum of the elements in the domain.
448
449 .. method:: vertices()
450
451 Return the vertices of the domain, as a list of rational instances of :class:`Point`.
452
453 .. method:: points()
454
455 Return the integer points of a bounded domain, as a list of integer instances of :class:`Point`.
456 If the domain is not bounded, a :exc:`ValueError` exception is raised.
457
458 .. method:: __contains__(point)
459
460 Return ``True`` if the point is contained within the domain.
461
462 .. method:: faces()
463
464 Return the list of faces of a bounded domain.
465 Each face is represented by a list of vertices, in the form of rational instances of :class:`Point`.
466 If the domain is not bounded, a :exc:`ValueError` exception is raised.
467
468 .. method:: plot(plot=None, **options)
469
470 Plot a 2D or 3D domain using `matplotlib <http://matplotlib.org/>`_.
471 Draw it to the current *plot* object if present, otherwise create a new one.
472 *options* are keyword arguments passed to the matplotlib drawing functions, they can be used to set the drawing color for example.
473 Raise :exc:`ValueError` is the domain is not 2D or 3D.
474
475 .. method:: subs(symbol, expression)
476 subs(pairs)
477
478 Substitute the given symbol by an expression in the domain constraints.
479 To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
480 The syntax of this function is similar to :func:`LinExpr.subs`.
481
482 .. classmethod:: fromstring(string)
483
484 Create a domain from a string.
485 Raise :exc:`SyntaxError` if the string is not properly formatted.
486
487 There are also methods to convert a domain to and from `SymPy <http://sympy.org>`_ expressions:
488
489 .. classmethod:: fromsympy(expr)
490
491 Create a domain from a sympy expression.
492
493 .. method:: tosympy()
494
495 Convert the domain to a sympy expression.
496
497
498 .. _reference_operators:
499
500 Comparison and Logic Operators
501 ------------------------------
502
503 The following functions create :class:`Polyhedron` or :class:`Domain` instances using the comparisons of two or more :class:`LinExpr` instances:
504
505 .. function:: Lt(expr1, expr2[, expr3, ...])
506
507 Create the polyhedron with constraints ``expr1 < expr2 < expr3 ...``.
508
509 .. function:: Le(expr1, expr2[, expr3, ...])
510
511 Create the polyhedron with constraints ``expr1 <= expr2 <= expr3 ...``.
512
513 .. function:: Eq(expr1, expr2[, expr3, ...])
514
515 Create the polyhedron with constraints ``expr1 == expr2 == expr3 ...``.
516
517 .. function:: Ne(expr1, expr2[, expr3, ...])
518
519 Create the domain such that ``expr1 != expr2 != expr3 ...``.
520 The result is a :class:`Domain` object, not a :class:`Polyhedron`.
521
522 .. function:: Ge(expr1, expr2[, expr3, ...])
523
524 Create the polyhedron with constraints ``expr1 >= expr2 >= expr3 ...``.
525
526 .. function:: Gt(expr1, expr2[, expr3, ...])
527
528 Create the polyhedron with constraints ``expr1 > expr2 > expr3 ...``.
529
530 The following functions combine :class:`Polyhedron` or :class:`Domain` instances using logic operators:
531
532 .. function:: And(domain1, domain2[, ...])
533
534 Create the intersection domain of the domains given in arguments.
535
536 .. function:: Or(domain1, domain2[, ...])
537
538 Create the union domain of the domains given in arguments.
539
540 .. function:: Not(domain)
541
542 Create the complementary domain of the domain given in argument.
543
544
545 .. _reference_geometry:
546
547 Geometric Objects
548 -----------------
549
550 .. class:: GeometricObject
551
552 :class:`GeometricObject` is an abstract class to represent objects with a geometric representation in space.
553 Subclasses of :class:`GeometricObject` are :class:`Polyhedron`, :class:`Domain` and :class:`Point`.
554 The following elements must be provided:
555
556 .. attribute:: symbols
557
558 The tuple of symbols present in the object expression, sorted according to :class:`Symbol.sortkey()`.
559
560 .. attribute:: dimension
561
562 The dimension of the object, i.e. the number of symbols present in it.
563
564 .. method:: aspolyedron()
565
566 Return a :class:`Polyhedron` object that approximates the geometric object.
567
568 .. method:: asdomain()
569
570 Return a :class:`Domain` object that approximates the geometric object.
571
572 .. class:: Point(coordinates)
573
574 Create a point from a dictionary or a sequence that maps the symbols to their coordinates.
575 Coordinates must be rational numbers.
576
577 For example, the point ``(x: 1, y: 2)`` can be constructed using one of the following instructions:
578
579 >>> x, y = symbols('x y')
580 >>> p = Point({x: 1, y: 2})
581 >>> p = Point([(x, 1), (y, 2)])
582
583 :class:`Point` instances are hashable and should be treated as immutable.
584
585 A point is a :class:`GeometricObject` instance.
586
587 .. attribute:: symbols
588
589 The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
590
591 .. attribute:: dimension
592
593 The dimension of the point, i.e. the number of symbols present in it.
594
595 .. method:: coordinate(symbol)
596 __getitem__(symbol)
597
598 Return the coordinate value of the given symbol.
599 Raise :exc:`KeyError` if the symbol is not involved in the point.
600
601 .. method:: coordinates()
602
603 Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
604
605 .. method:: values()
606
607 Iterate over the coordinate values in the point.
608
609 .. method:: isorigin()
610
611 Return ``True`` if all coordinates are ``0``.
612
613 .. method:: __bool__()
614
615 Return ``True`` if not all coordinates are ``0``.
616
617 .. method:: __add__(vector)
618
619 Translate the point by a :class:`Vector` object and return the resulting point.
620
621 .. method:: __sub__(point)
622 __sub__(vector)
623
624 The first version substracts a point from another and returns the resulting vector.
625 The second version translates the point by the opposite vector of *vector* and returns the resulting point.
626
627 .. method:: __eq__(point)
628
629 Test whether two points are equal.
630
631
632 .. class:: Vector(coordinates)
633 Vector(point1, point2)
634
635 The first version creates a vector from a dictionary or a sequence that maps the symbols to their coordinates, similarly to :meth:`Point`.
636 The second version creates a vector between two points.
637
638 :class:`Vector` instances are hashable and should be treated as immutable.
639
640 .. attribute:: symbols
641
642 The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
643
644 .. attribute:: dimension
645
646 The dimension of the point, i.e. the number of symbols present in it.
647
648 .. method:: coordinate(symbol)
649 __getitem__(symbol)
650
651 Return the coordinate value of the given symbol.
652 Raise :exc:`KeyError` if the symbol is not involved in the point.
653
654 .. method:: coordinates()
655
656 Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
657
658 .. method:: values()
659
660 Iterate over the coordinate values in the point.
661
662 .. method:: isnull()
663
664 Return ``True`` if all coordinates are ``0``.
665
666 .. method:: __bool__()
667
668 Return ``True`` if not all coordinates are ``0``.
669
670 .. method:: __add__(point)
671 __add__(vector)
672
673 The first version translates the point *point* to the vector and returns the resulting point.
674 The second version adds vector *vector* to the vector and returns the resulting vector.
675
676 .. method:: __sub__(point)
677 __sub__(vector)
678
679 The first version substracts a point from a vector and returns the resulting point.
680 The second version returns the difference vector between two vectors.
681
682 .. method:: __neg__()
683
684 Return the opposite vector.
685
686 .. method:: __mul__(value)
687
688 Multiply the vector by a scalar value and return the resulting vector.
689
690 .. method:: __truediv__(value)
691
692 Divide the vector by a scalar value and return the resulting vector.
693
694 .. method:: __eq__(vector)
695
696 Test whether two vectors are equal.
697
698 .. method:: angle(vector)
699
700 Retrieve the angle required to rotate the vector into the vector passed in argument.
701 The result is an angle in radians, ranging between ``-pi`` and ``pi``.
702
703 .. method:: cross(vector)
704
705 Compute the cross product of two 3D vectors.
706 If either one of the vectors is not three-dimensional, a :exc:`ValueError` exception is raised.
707
708 .. method:: dot(vector)
709
710 Compute the dot product of two vectors.
711
712 .. method:: norm()
713
714 Return the norm of the vector.
715
716 .. method:: norm2()
717
718 Return the squared norm of the vector.
719
720 .. method:: asunit()
721
722 Return the normalized vector, i.e. the vector of same direction but with norm 1.