Linear Functions and Constraints
This module implements linear functions (see LinearFunction) in formal variables and chained (in)equalities between them (see LinearConstraint). By convention, these are always written as either equalities or less-or-equal. For example:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
doctest:...: DeprecationWarning: The default value of 'nonnegative' will change, to False instead of True. You should add the explicit 'nonnegative=True'.
See http://trac.sagemath.org/15521 for details.
sage: f = 1 + x[1] + 2*x[2]; f # a linear function
1 + x_0 + 2*x_1
sage: type(f)
<type 'sage.numerical.linear_functions.LinearFunction'>
sage: c = (0 <= f); c # a constraint
0 <= 1 + x_0 + 2*x_1
sage: type(c)
<type 'sage.numerical.linear_functions.LinearConstraint'>
Note that you can use this module without any reference to linear programming, it only implements linear functions over a base ring and constraints. However, for ease of demonstration we will always construct them out of linear programs (see mip).
Constraints can be equations or (non-strict) inequalities. They can be chained:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: x[0] == x[1] == x[2] == x[3]
x_0 == x_1 == x_2 == x_3
sage: ieq_01234 = x[0] <= x[1] <= x[2] <= x[3] <= x[4]
sage: ieq_01234
x_0 <= x_1 <= x_2 <= x_3 <= x_4
If necessary, the direction of inequality is flipped to always write inequalities as less or equal:
sage: x[5] >= ieq_01234
x_0 <= x_1 <= x_2 <= x_3 <= x_4 <= x_5
sage: (x[5]<=x[6]) >= ieq_01234
x_0 <= x_1 <= x_2 <= x_3 <= x_4 <= x_5 <= x_6
sage: (x[5]<=x[6]) <= ieq_01234
x_5 <= x_6 <= x_0 <= x_1 <= x_2 <= x_3 <= x_4
TESTS:
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: b[0] <= b[1] <= 2
x_0 <= x_1 <= 2
sage: list(b[0] <= b[1] <= 2)
[x_0, x_1, 2]
sage: 1 >= b[1] >= 2*b[0]
2*x_0 <= x_1 <= 1
sage: b[2] >= b[1] >= 2*b[0]
2*x_0 <= x_1 <= x_2
Bases: sage.structure.element.Element
A class to represent formal Linear Constraints.
A Linear Constraint being an inequality between two linear functions, this class lets the user write LinearFunction1 <= LinearFunction2 to define the corresponding constraint, which can potentially involve several layers of such inequalities ((A <= B <= C), or even equalities like A == B.
Trivial constraints (meaning that they have only one term and no relation) are also allowed. They are required for the coercion system to work.
Warning
This class has no reason to be instanciated by the user, and is meant to be used by instances of MixedIntegerLinearProgram.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: b[2]+2*b[3] <= b[8]-5
x_0 + 2*x_1 <= -5 + x_2
Compare left and right.
OUTPUT:
Boolean. Whether all terms of left and right are equal. Note that this is stronger than mathematical equivalence of the relations.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: (x[1] + 1 >= 2).equals(3/3 + 1*x[1] + 0*x[2] >= 8/4)
True
sage: (x[1] + 1 >= 2).equals(x[1] + 1-1 >= 1-1)
False
Iterate over the unchained(!) equations
OUTPUT:
An iterator over pairs (lhs, rhs) such that the individual equations are lhs == rhs.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: eqns = 1 == b[0] == b[2] == 3 == b[3]; eqns
1 == x_0 == x_1 == 3 == x_2
sage: for lhs, rhs in eqns.equations():
... print str(lhs) + ' == ' + str(rhs)
1 == x_0
x_0 == x_1
x_1 == 3
3 == x_2
Iterate over the unchained(!) inequalities
OUTPUT:
An iterator over pairs (lhs, rhs) such that the individual equations are lhs <= rhs.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: ieq = 1 <= b[0] <= b[2] <= 3 <= b[3]; ieq
1 <= x_0 <= x_1 <= 3 <= x_2
sage: for lhs, rhs in ieq.inequalities():
... print str(lhs) + ' <= ' + str(rhs)
1 <= x_0
x_0 <= x_1
x_1 <= 3
3 <= x_2
Whether the constraint is a chained equation
OUTPUT:
Boolean.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: (b[0] == b[1]).is_equation()
True
sage: (b[0] <= b[1]).is_equation()
False
Whether the constraint is a chained less-or_equal inequality
OUTPUT:
Boolean.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: (b[0] == b[1]).is_less_or_equal()
False
sage: (b[0] <= b[1]).is_less_or_equal()
True
Test whether the constraint is trivial.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: LC = p.linear_constraints_parent()
sage: ieq = LC(1,2); ieq
1 <= 2
sage: ieq.is_trivial()
False
sage: ieq = LC(1); ieq
trivial constraint starting with 1
sage: ieq.is_trivial()
True
Return the parent for linear functions over base_ring.
The output is cached, so only a single parent is ever constructed for a given base ring.
INPUT:
- linear_functions_parent – a LinearFunctionsParent_class. The type of linear functions that the constraints are made out of.
OUTPUT:
The parent of the linear constraints with the given linear functions.
EXAMPLES:
sage: from sage.numerical.linear_functions import ... LinearFunctionsParent, LinearConstraintsParent sage: LF = LinearFunctionsParent(QQ) sage: LinearConstraintsParent(LF) Linear constraints over Rational Field
Bases: sage.structure.parent.Parent
Parent for LinearConstraint
Warning
This class has no reason to be instanciated by the user, and is meant to be used by instances of MixedIntegerLinearProgram. Also, use the LinearConstraintsParent() factory function.
INPUT/OUTPUT:
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: LC = p.linear_constraints_parent(); LC
Linear constraints over Real Double Field
sage: from sage.numerical.linear_functions import LinearConstraintsParent
sage: LinearConstraintsParent(p.linear_functions_parent()) is LC
True
Return the parent for the linear functions
EXAMPLES:
sage: LC = MixedIntegerLinearProgram().linear_constraints_parent()
sage: LC.linear_functions_parent()
Linear functions over Real Double Field
Bases: sage.structure.element.ModuleElement
An elementary algebra to represent symbolic linear functions.
Warning
You should never instantiate LinearFunction manually. Use the element constructor in the parent instead. For convenience, you can also call the MixedIntegerLinearProgram instance directly.
EXAMPLES:
For example, do this:
sage: p = MixedIntegerLinearProgram()
sage: p({0 : 1, 3 : -8})
x_0 - 8*x_3
or this:
sage: parent = p.linear_functions_parent()
sage: parent({0 : 1, 3 : -8})
x_0 - 8*x_3
instead of this:
sage: from sage.numerical.linear_functions import LinearFunction
sage: LinearFunction(p.linear_functions_parent(), {0 : 1, 3 : -8})
x_0 - 8*x_3
Return one of the the coefficients.
INPUT:
OUTPUT:
A base ring element. The coefficient of x in the linear function. Pass -1 for the constant term.
EXAMPLE:
sage: mip.<b> = MixedIntegerLinearProgram()
sage: lf = -8 * b[3] + b[0] - 5; lf
-5 - 8*x_0 + x_1
sage: lf.coefficient(b[3])
-8.0
sage: lf.coefficient(0) # x_0 is b[3]
-8.0
sage: lf.coefficient(4)
0.0
sage: lf.coefficient(-1)
-5.0
TESTS:
sage: lf.coefficient(b[3] + b[4])
Traceback (most recent call last):
...
ValueError: x is a sum, must be a single variable
sage: lf.coefficient(2*b[3])
Traceback (most recent call last):
...
ValueError: x must have a unit coefficient
sage: mip.<q> = MixedIntegerLinearProgram(solver='ppl')
sage: lf.coefficient(q[0])
Traceback (most recent call last):
...
ValueError: x is from a different linear functions module
Return the dictionary corresponding to the Linear Function.
OUTPUT:
The linear function is represented as a dictionary. The value are the coefficient of the variable represented by the keys ( which are integers ). The key -1 corresponds to the constant term.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: lf = p({0 : 1, 3 : -8})
sage: lf.dict()
{0: 1.0, 3: -8.0}
Logically compare left and right.
OUTPUT:
Boolean.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: (x[1] + 1).equals(3/3 + 1*x[1] + 0*x[2])
True
Test whether self is zero.
OUTPUT:
Boolean.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: (x[1] - x[1] + 0*x[2]).is_zero()
True
Iterate over the index, coefficient pairs
OUTPUT:
An iterator over the (key, coefficient) pairs. The keys are integers indexing the variables. The key -1 corresponds to the constant term.
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver = 'ppl')
sage: x = p.new_variable()
sage: f = 0.5 + 3/2*x[1] + 0.6*x[3]
sage: for id, coeff in f.iteritems():
... print 'id =', id, ' coeff =', coeff
id = 0 coeff = 3/2
id = 1 coeff = 3/5
id = -1 coeff = 1/2
Return the parent for linear functions over base_ring.
The output is cached, so only a single parent is ever constructed for a given base ring.
INPUT:
OUTPUT:
The parent of the linear functions over base_ring.
EXAMPLES:
sage: from sage.numerical.linear_functions import LinearFunctionsParent
sage: LinearFunctionsParent(QQ)
Linear functions over Rational Field
Bases: sage.structure.parent.Parent
The parent for all linear functions over a fixed base ring.
Warning
You should use LinearFunctionsParent() to construct instances of this class.
INPUT/OUTPUT:
EXAMPLES:
sage: from sage.numerical.linear_functions import LinearFunctionsParent_class
sage: LinearFunctionsParent_class
<type 'sage.numerical.linear_functions.LinearFunctionsParent_class'>
Return the linear variable \(x_i\).
INPUT:
OUTPUT:
The linear function \(x_i\).
EXAMPLES:
sage: LF = MixedIntegerLinearProgram().linear_functions_parent()
sage: LF.gen(23)
x_23
Set the multiplication symbol when pretty-printing linear functions.
INPUT:
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: f = -1-2*x[0]-3*x[1]
sage: LF = f.parent()
sage: LF._get_multiplication_symbol()
'*'
sage: f
-1 - 2*x_0 - 3*x_1
sage: LF.set_multiplication_symbol(' ')
sage: f
-1 - 2 x_0 - 3 x_1
sage: LF.set_multiplication_symbol()
sage: f
-1 - 2*x_0 - 3*x_1
Return the tensor product with free_module.
INPUT:
OUTPUT:
Instance of sage.numerical.linear_tensor.LinearTensorParent_class.
EXAMPLES:
sage: LF = MixedIntegerLinearProgram().linear_functions_parent()
sage: LF.tensor(RDF^3)
Tensor product of Vector space of dimension 3 over Real Double Field
and Linear functions over Real Double Field
sage: LF.tensor(QQ^2)
Traceback (most recent call last):
...
ValueError: base rings must match
Test whether x is a linear constraint
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: ieq = (x[0] <= x[1])
sage: from sage.numerical.linear_functions import is_LinearConstraint
sage: is_LinearConstraint(ieq)
True
sage: is_LinearConstraint('a string')
False
Test whether x is a linear function
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: from sage.numerical.linear_functions import is_LinearFunction
sage: is_LinearFunction(x[0] - 2*x[2])
True
sage: is_LinearFunction('a string')
False