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()
sage: f = 1 + x[1] + 2*x[2]; f # a linear function
1 + x_0 + 2*x_1
sage: type(f)
<class 'sage.numerical.linear_functions.LinearFunction'>
sage: c = (0 <= f); c # a constraint
0 <= 1 + x_0 + 2*x_1
sage: type(c)
<class '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
Warning
The implementation of chained inequalities uses a Python hack to make it work, so it is not completely robust. In particular, while constants are allowed, no two constants can appear next to each other. The following does not work for example:
sage: x[0] <= 3 <= 4
True
If you really need this for some reason, you can explicitly convert
the constants to a LinearFunction
:
sage: from sage.numerical.linear_functions import LinearFunctionsParent
sage: LF = LinearFunctionsParent(QQ)
sage: x[1] <= LF(3) <= LF(4)
x_1 <= 3 <= 4
- class sage.numerical.linear_functions.LinearConstraint#
Bases:
sage.numerical.linear_functions.LinearFunctionOrConstraint
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 likeA == B == C
.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 instantiated by the user, and is meant to be used by instances of
MixedIntegerLinearProgram
.INPUT:
parent
– the parent, aLinearConstraintsParent_class
terms
– a list/tuple/iterable of two or more linear functions (or things that can be converted into linear functions).equality
– boolean (default:False
). Whether the terms are the entries of a chained less-or-equal (<=
) inequality or a chained equality.
EXAMPLES:
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
- equals(left, right)#
Compare
left
andright
.OUTPUT:
Boolean. Whether all terms of
left
andright
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
- equations()#
Iterate over the unchained(!) equations
OUTPUT:
An iterator over pairs
(lhs, rhs)
such that the individual equations arelhs == 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
- inequalities()#
Iterate over the unchained(!) inequalities
OUTPUT:
An iterator over pairs
(lhs, rhs)
such that the individual equations arelhs <= 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
- is_equation()#
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
- is_less_or_equal()#
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
- is_trivial()#
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
- sage.numerical.linear_functions.LinearConstraintsParent(linear_functions_parent)#
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
– aLinearFunctionsParent_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
- class sage.numerical.linear_functions.LinearConstraintsParent_class#
Bases:
sage.structure.parent.Parent
Parent for
LinearConstraint
Warning
This class has no reason to be instantiated by the user, and is meant to be used by instances of
MixedIntegerLinearProgram
. Also, use theLinearConstraintsParent()
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
- linear_functions_parent()#
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
- class sage.numerical.linear_functions.LinearFunction#
Bases:
sage.numerical.linear_functions.LinearFunctionOrConstraint
An elementary algebra to represent symbolic linear functions.
Warning
You should never instantiate
LinearFunction
manually. Use the element constructor in the parent instead.EXAMPLES:
For example, do this:
sage: p = MixedIntegerLinearProgram() 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
- coefficient(x)#
Return one of the coefficients.
INPUT:
x
– a linear variable or an integer. If an integer \(i\) is passed, then \(x_i\) is used as linear variable.
OUTPUT:
A base ring element. The coefficient of
x
in the linear function. Pass-1
for the constant term.EXAMPLES:
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
- dict()#
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.EXAMPLES:
sage: p = MixedIntegerLinearProgram() sage: LF = p.linear_functions_parent() sage: lf = LF({0 : 1, 3 : -8}) sage: lf.dict() {0: 1.0, 3: -8.0}
- equals(left, right)#
Logically compare
left
andright
.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
- is_zero()#
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
- iteritems()#
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 sorted(f.iteritems()): ....: print('id = {} coeff = {}'.format(id, coeff)) id = -1 coeff = 1/2 id = 0 coeff = 3/2 id = 1 coeff = 3/5
- class sage.numerical.linear_functions.LinearFunctionOrConstraint#
Bases:
sage.structure.element.ModuleElement
Base class for
LinearFunction
andLinearConstraint
.This class exists solely to implement chaining of inequalities in constraints.
- sage.numerical.linear_functions.LinearFunctionsParent(base_ring)#
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:
base_ring
– a ring. The coefficient ring for the linear functions.
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
- class sage.numerical.linear_functions.LinearFunctionsParent_class#
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 <class 'sage.numerical.linear_functions.LinearFunctionsParent_class'>
- gen(i)#
Return the linear variable \(x_i\).
INPUT:
i
– non-negative integer.
OUTPUT:
The linear function \(x_i\).
EXAMPLES:
sage: LF = MixedIntegerLinearProgram().linear_functions_parent() sage: LF.gen(23) x_23
- set_multiplication_symbol(symbol='*')#
Set the multiplication symbol when pretty-printing linear functions.
INPUT:
symbol
– string, default:'*'
. The multiplication symbol to be used.
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
- tensor(free_module)#
Return the tensor product with
free_module
.INPUT:
free_module
– vector space or matrix space over the same base ring.
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
- sage.numerical.linear_functions.is_LinearConstraint(x)#
Test whether
x
is a linear constraintINPUT:
x
– anything.
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
- sage.numerical.linear_functions.is_LinearFunction(x)#
Test whether
x
is a linear functionINPUT:
x
– anything.
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