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