.. _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.