.. _reference:
Module Reference
================
.. _reference_symbols:
Symbols
-------
*Symbols* are the basic components to build expressions and constraints.
They correspond to mathematical variables.
.. class:: Symbol(name)
Return a symbol with the name string given in argument.
Alternatively, the function :func:`symbols` allows to create several symbols at once.
Symbols are instances of class :class:`LinExpr` and inherit its functionalities.
>>> x = Symbol('x')
>>> x
x
Two instances of :class:`Symbol` are equal if they have the same name.
.. attribute:: name
The name of the symbol.
.. method:: asdummy()
Return a new :class:`Dummy` symbol instance with the same name.
.. method:: sortkey()
Return a sorting key for the symbol.
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`).
>>> sort(symbols, key=Symbol.sortkey)
.. function:: symbols(names)
This function returns a tuple of symbols whose names are taken from a comma or whitespace delimited string, or a sequence of strings.
It is useful to define several symbols at once.
>>> x, y = symbols('x y')
>>> x, y = symbols('x, y')
>>> x, y = symbols(['x', 'y'])
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.
This is achieved using ``Dummy('x')``.
.. class:: Dummy(name=None)
A variation of :class:`Symbol` in which all symbols are unique and identified by an internal count index.
If a name is not supplied then a string value of the count index will be used.
This is useful when a unique, temporary variable is needed and the name of the variable used in the expression is not important.
Unlike :class:`Symbol`, :class:`Dummy` instances with the same name are not equal:
>>> x = Symbol('x')
>>> x1, x2 = Dummy('x'), Dummy('x')
>>> x == x1
False
>>> x1 == x2
False
>>> x1 == x1
True
.. _reference_linexprs:
Linear Expressions
------------------
A *linear expression* consists of a list of coefficient-variable pairs that capture the linear terms, plus a constant term.
Linear expressions are used to build constraints. They are temporary objects that typically have short lifespans.
Linear expressions are generally built using overloaded operators.
For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :class:`LinExpr`.
.. class:: LinExpr(coefficients=None, constant=0)
LinExpr(string)
Return a linear expression from a dictionary or a sequence, that maps symbols to their coefficients, and a constant term.
The coefficients and the constant term must be rational numbers.
For example, the linear expression ``x + 2*y + 1`` can be constructed using one of the following instructions:
>>> x, y = symbols('x y')
>>> LinExpr({x: 1, y: 2}, 1)
>>> LinExpr([(x, 1), (y, 2)], 1)
However, it may be easier to use overloaded operators:
>>> x, y = symbols('x y')
>>> x + 2*y + 1
Alternatively, linear expressions can be constructed from a string:
>>> LinExpr('x + 2y + 1')
:class:`LinExpr` instances are hashable, and should be treated as immutable.
A linear expression with a single symbol of coefficient 1 and no constant term is automatically subclassed as a :class:`Symbol` instance.
A linear expression with no symbol, only a constant term, is automatically subclassed as a :class:`Rational` instance.
.. method:: coefficient(symbol)
__getitem__(symbol)
Return the coefficient value of the given symbol, or ``0`` if the symbol does not appear in the expression.
.. method:: coefficients()
Iterate over the pairs ``(symbol, value)`` of linear terms in the expression.
The constant term is ignored.
.. attribute:: constant
The constant term of the expression.
.. attribute:: symbols
The tuple of symbols present in the expression, sorted according to :meth:`Symbol.sortkey`.
.. attribute:: dimension
The dimension of the expression, i.e. the number of symbols present in it.
.. method:: isconstant()
Return ``True`` if the expression only consists of a constant term.
In this case, it is a :class:`Rational` instance.
.. method:: issymbol()
Return ``True`` if an expression only consists of a symbol with coefficient ``1``.
In this case, it is a :class:`Symbol` instance.
.. method:: values()
Iterate over the coefficient values in the expression, and the constant term.
.. method:: __add__(expr)
Return the sum of two linear expressions.
.. method:: __sub__(expr)
Return the difference between two linear expressions.
.. method:: __mul__(value)
Return the product of the linear expression by a rational.
.. method:: __truediv__(value)
Return the quotient of the linear expression by a rational.
.. method:: __eq__(expr)
Test whether two linear expressions are equal.
Unlike methods :meth:`LinExpr.__lt__`, :meth:`LinExpr.__le__`, :meth:`LinExpr.__ge__`, :meth:`LinExpr.__gt__`, the result is a boolean value, not a polyhedron.
To express that two linear expressions are equal or not equal, use functions :func:`Eq` and :func:`Ne` instead.
As explained below, it is possible to create polyhedra from linear expressions using comparison methods.
.. method:: __lt__(expr)
__le__(expr)
__ge__(expr)
__gt__(expr)
Create a new :class:`Polyhedron` instance whose unique constraint is the comparison between two linear expressions.
As an alternative, functions :func:`Lt`, :func:`Le`, :func:`Ge` and :func:`Gt` can be used.
>>> x, y = symbols('x y')
>>> x < y
x + 1 <= y
.. method:: scaleint()
Return the expression multiplied by its lowest common denominator to make all values integer.
.. method:: subs(symbol, expression)
subs(pairs)
Substitute the given symbol by an expression and return the resulting expression.
Raise :exc:`TypeError` if the resulting expression is not linear.
>>> x, y = symbols('x y')
>>> e = x + 2*y + 1
>>> e.subs(y, x - 1)
3*x - 1
To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
>>> e.subs({x: y, y: x})
2*x + y + 1
.. classmethod:: fromstring(string)
Create an expression from a string.
Raise :exc:`SyntaxError` if the string is not properly formatted.
There are also methods to convert linear expressions to and from `SymPy `_ expressions:
.. classmethod:: fromsympy(expr)
Create a linear expression from a :mod:`sympy` expression.
Raise :exc:`TypeError` is the :mod:`sympy` expression is not linear.
.. method:: tosympy()
Convert the linear expression to a sympy expression.
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.
They are implemented by the :class:`Rational` class, that inherits from both :class:`LinExpr` and :class:`fractions.Fraction` classes.
.. class:: Rational(numerator, denominator=1)
Rational(string)
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``.
If the denominator is ``0``, it raises a :exc:`ZeroDivisionError`.
The other version of the constructor expects a string.
The usual form for this instance is::
[sign] numerator ['/' denominator]
where the optional ``sign`` may be either '+' or '-' and the ``numerator`` and ``denominator`` (if present) are strings of decimal digits.
See the documentation of :class:`fractions.Fraction` for more information and examples.
.. _reference_polyhedra:
Polyhedra
---------
A *convex polyhedron* (or simply "polyhedron") is the space defined by a system of linear equalities and inequalities.
This space can be unbounded.
A *Z-polyhedron* (simply called "polyhedron" in LinPy) is the set of integer points in a convex polyhedron.
.. class:: Polyhedron(equalities, inequalities)
Polyhedron(string)
Polyhedron(geometric object)
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``.
For example, the polyhedron ``0 <= x <= 2, 0 <= y <= 2`` can be constructed with:
>>> x, y = symbols('x y')
>>> square1 = Polyhedron([], [x, 2 - x, y, 2 - y])
>>> square1
And(0 <= x, x <= 2, 0 <= y, y <= 2)
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:
>>> x, y = symbols('x y')
>>> square1 = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2)
>>> square1 = Le(0, x, 2) & Le(0, y, 2)
It is also possible to build a polyhedron from a string.
>>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
Finally, a polyhedron can be constructed from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.aspolyedron` method.
This way, it is possible to compute the polyhedral hull of a :class:`Domain` instance, i.e., the convex hull of two polyhedra:
>>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
>>> square2 = Polyhedron('1 <= x <= 3, 1 <= y <= 3')
>>> Polyhedron(square1 | square2)
And(0 <= x, 0 <= y, x <= y + 2, y <= x + 2, x <= 3, y <= 3)
A polyhedron is a :class:`Domain` instance, and, therefore, inherits the functionalities of this class.
It is also a :class:`GeometricObject` instance.
.. attribute:: equalities
The tuple of equalities.
This is a list of :class:`LinExpr` instances that are equal to ``0`` in the polyhedron.
.. attribute:: inequalities
The tuple of inequalities.
This is a list of :class:`LinExpr` instances that are greater or equal to ``0`` in the polyhedron.
.. attribute:: constraints
The tuple of constraints, i.e., equalities and inequalities.
This is semantically equivalent to: ``equalities + inequalities``.
.. method:: convex_union(polyhedron[, ...])
Return the convex union of two or more polyhedra.
.. method:: asinequalities()
Express the polyhedron using inequalities, given as a list of expressions greater or equal to 0.
.. method:: widen(polyhedron)
Compute the *standard widening* of two polyhedra, à la Halbwachs.
In its current implementation, this method is slow and should not be used on large polyhedra.
.. data:: Empty
The empty polyhedron, whose set of constraints is not satisfiable.
.. data:: Universe
The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.
.. _reference_domains:
Domains
-------
A *domain* is a union of polyhedra.
Unlike polyhedra, domains allow exact computation of union, subtraction and complementary operations.
.. class:: Domain(*polyhedra)
Domain(string)
Domain(geometric object)
Return a domain from a sequence of polyhedra.
>>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
>>> square2 = Polyhedron('1 <= x <= 3, 1 <= y <= 3')
>>> dom = Domain(square1, square2)
>>> dom
Or(And(x <= 2, 0 <= x, y <= 2, 0 <= y), And(x <= 3, 1 <= x, y <= 3, 1 <= y))
It is also possible to build domains from polyhedra using arithmetic operators :meth:`Domain.__or__`, :meth:`Domain.__invert__` or functions :func:`Or` and :func:`Not`, using one of the following instructions:
>>> dom = square1 | square2
>>> dom = Or(square1, square2)
Alternatively, a domain can be built from a string:
>>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 1 <= x <= 3, 1 <= y <= 3')
Finally, a domain can be built from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method.
A domain is also a :class:`GeometricObject` instance.
A domain with a unique polyhedron is automatically subclassed as a :class:`Polyhedron` instance.
.. attribute:: polyhedra
The tuple of polyhedra present in the domain.
.. attribute:: symbols
The tuple of symbols present in the domain equations, sorted according to :meth:`Symbol.sortkey`.
.. attribute:: dimension
The dimension of the domain, i.e. the number of symbols present in it.
.. method:: isempty()
Return ``True`` if the domain is empty, that is, equal to :data:`Empty`.
.. method:: __bool__()
Return ``True`` if the domain is non-empty.
.. method:: isuniverse()
Return ``True`` if the domain is universal, that is, equal to :data:`Universe`.
.. method:: isbounded()
Return ``True`` is the domain is bounded.
.. method:: __eq__(domain)
Return ``True`` if two domains are equal.
.. method:: isdisjoint(domain)
Return ``True`` if two domains have a null intersection.
.. method:: issubset(domain)
__le__(domain)
Report whether another domain contains the domain.
.. method:: __lt__(domain)
Report whether another domain is contained within the domain.
.. method:: complement()
__invert__()
Return the complementary domain of the domain.
.. method:: make_disjoint()
Return an equivalent domain, whose polyhedra are disjoint.
.. method:: coalesce()
Simplify the representation of the domain by trying to combine pairs of polyhedra into a single polyhedron, and return the resulting domain.
.. method:: detect_equalities()
Simplify the representation of the domain by detecting implicit equalities, and return the resulting domain.
.. method:: remove_redundancies()
Remove redundant constraints in the domain, and return the resulting domain.
.. method:: project(symbols)
Project out the sequence of symbols given in arguments, and return the resulting domain.
.. method:: sample()
Return a sample of the domain, as an integer instance of :class:`Point`.
If the domain is empty, a :exc:`ValueError` exception is raised.
.. method:: intersection(domain[, ...])
__and__(domain)
Return the intersection of two or more domains as a new domain.
As an alternative, function :func:`And` can be used.
.. method:: union(domain[, ...])
__or__(domain)
__add__(domain)
Return the union of two or more domains as a new domain.
As an alternative, function :func:`Or` can be used.
.. method:: difference(domain)
__sub__(domain)
Return the difference between two domains as a new domain.
.. method:: lexmin()
Return the lexicographic minimum of the elements in the domain.
.. method:: lexmax()
Return the lexicographic maximum of the elements in the domain.
.. method:: vertices()
Return the vertices of the domain, as a list of rational instances of :class:`Point`.
.. method:: points()
Return the integer points of a bounded domain, as a list of integer instances of :class:`Point`.
If the domain is not bounded, a :exc:`ValueError` exception is raised.
.. method:: __contains__(point)
Return ``True`` if the point is contained within the domain.
.. method:: faces()
Return the list of faces of a bounded domain.
Each face is represented by a list of vertices, in the form of rational instances of :class:`Point`.
If the domain is not bounded, a :exc:`ValueError` exception is raised.
.. method:: plot(plot=None, **options)
Plot a 2D or 3D domain using `matplotlib `_.
Draw it to the current *plot* object if present, otherwise create a new one.
*options* are keyword arguments passed to the matplotlib drawing functions, they can be used to set the drawing color for example.
Raise :exc:`ValueError` is the domain is not 2D or 3D.
.. method:: subs(symbol, expression)
subs(pairs)
Substitute the given symbol by an expression in the domain constraints.
To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
The syntax of this function is similar to :func:`LinExpr.subs`.
.. classmethod:: fromstring(string)
Create a domain from a string.
Raise :exc:`SyntaxError` if the string is not properly formatted.
There are also methods to convert a domain to and from `SymPy `_ expressions:
.. classmethod:: fromsympy(expr)
Create a domain from a sympy expression.
.. method:: tosympy()
Convert the domain to a sympy expression.
.. _reference_operators:
Comparison and Logic Operators
------------------------------
The following functions create :class:`Polyhedron` or :class:`Domain` instances using the comparisons of two or more :class:`LinExpr` instances:
.. function:: Lt(expr1, expr2[, expr3, ...])
Create the polyhedron with constraints ``expr1 < expr2 < expr3 ...``.
.. function:: Le(expr1, expr2[, expr3, ...])
Create the polyhedron with constraints ``expr1 <= expr2 <= expr3 ...``.
.. function:: Eq(expr1, expr2[, expr3, ...])
Create the polyhedron with constraints ``expr1 == expr2 == expr3 ...``.
.. function:: Ne(expr1, expr2[, expr3, ...])
Create the domain such that ``expr1 != expr2 != expr3 ...``.
The result is a :class:`Domain` object, not a :class:`Polyhedron`.
.. function:: Ge(expr1, expr2[, expr3, ...])
Create the polyhedron with constraints ``expr1 >= expr2 >= expr3 ...``.
.. function:: Gt(expr1, expr2[, expr3, ...])
Create the polyhedron with constraints ``expr1 > expr2 > expr3 ...``.
The following functions combine :class:`Polyhedron` or :class:`Domain` instances using logic operators:
.. function:: And(domain1, domain2[, ...])
Create the intersection domain of the domains given in arguments.
.. function:: Or(domain1, domain2[, ...])
Create the union domain of the domains given in arguments.
.. function:: Not(domain)
Create the complementary domain of the domain given in argument.
.. _reference_geometry:
Geometric Objects
-----------------
.. class:: GeometricObject
:class:`GeometricObject` is an abstract class to represent objects with a geometric representation in space.
Subclasses of :class:`GeometricObject` are :class:`Polyhedron`, :class:`Domain` and :class:`Point`.
The following elements must be provided:
.. attribute:: symbols
The tuple of symbols present in the object expression, sorted according to :class:`Symbol.sortkey()`.
.. attribute:: dimension
The dimension of the object, i.e. the number of symbols present in it.
.. method:: aspolyedron()
Return a :class:`Polyhedron` object that approximates the geometric object.
.. method:: asdomain()
Return a :class:`Domain` object that approximates the geometric object.
.. class:: Point(coordinates)
Create a point from a dictionary or a sequence that maps the symbols to their coordinates.
Coordinates must be rational numbers.
For example, the point ``(x: 1, y: 2)`` can be constructed using one of the following instructions:
>>> x, y = symbols('x y')
>>> p = Point({x: 1, y: 2})
>>> p = Point([(x, 1), (y, 2)])
:class:`Point` instances are hashable and should be treated as immutable.
A point is a :class:`GeometricObject` instance.
.. attribute:: symbols
The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
.. attribute:: dimension
The dimension of the point, i.e. the number of symbols present in it.
.. method:: coordinate(symbol)
__getitem__(symbol)
Return the coordinate value of the given symbol.
Raise :exc:`KeyError` if the symbol is not involved in the point.
.. method:: coordinates()
Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
.. method:: values()
Iterate over the coordinate values in the point.
.. method:: isorigin()
Return ``True`` if all coordinates are ``0``.
.. method:: __bool__()
Return ``True`` if not all coordinates are ``0``.
.. method:: __add__(vector)
Translate the point by a :class:`Vector` object and return the resulting point.
.. method:: __sub__(point)
__sub__(vector)
The first version substracts a point from another and returns the resulting vector.
The second version translates the point by the opposite vector of *vector* and returns the resulting point.
.. method:: __eq__(point)
Test whether two points are equal.
.. class:: Vector(coordinates)
Vector(point1, point2)
The first version creates a vector from a dictionary or a sequence that maps the symbols to their coordinates, similarly to :meth:`Point`.
The second version creates a vector between two points.
:class:`Vector` instances are hashable and should be treated as immutable.
.. attribute:: symbols
The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
.. attribute:: dimension
The dimension of the point, i.e. the number of symbols present in it.
.. method:: coordinate(symbol)
__getitem__(symbol)
Return the coordinate value of the given symbol.
Raise :exc:`KeyError` if the symbol is not involved in the point.
.. method:: coordinates()
Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
.. method:: values()
Iterate over the coordinate values in the point.
.. method:: isnull()
Return ``True`` if all coordinates are ``0``.
.. method:: __bool__()
Return ``True`` if not all coordinates are ``0``.
.. method:: __add__(point)
__add__(vector)
The first version translates the point *point* to the vector and returns the resulting point.
The second version adds vector *vector* to the vector and returns the resulting vector.
.. method:: __sub__(point)
__sub__(vector)
The first version substracts a point from a vector and returns the resulting point.
The second version returns the difference vector between two vectors.
.. method:: __neg__()
Return the opposite vector.
.. method:: __mul__(value)
Multiply the vector by a scalar value and return the resulting vector.
.. method:: __truediv__(value)
Divide the vector by a scalar value and return the resulting vector.
.. method:: __eq__(vector)
Test whether two vectors are equal.
.. method:: angle(vector)
Retrieve the angle required to rotate the vector into the vector passed in argument.
The result is an angle in radians, ranging between ``-pi`` and ``pi``.
.. method:: cross(vector)
Compute the cross product of two 3D vectors.
If either one of the vectors is not three-dimensional, a :exc:`ValueError` exception is raised.
.. method:: dot(vector)
Compute the dot product of two vectors.
.. method:: norm()
Return the norm of the vector.
.. method:: norm2()
Return the squared norm of the vector.
.. method:: asunit()
Return the normalized vector, i.e. the vector of same direction but with norm 1.