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