Mixed Integer Linear Programming¶
This module implements classes and methods for the efficient solving of Linear Programs (LP) and Mixed Integer Linear Programs (MILP).
Do you want to understand how the simplex method works? See the
interactive_simplex_method
module (educational purposes
only)
Definition¶
A linear program (LP) is an optimization problem (Wikipedia article Optimization_(mathematics)) in the following form
with given \(A \in \mathbb{R}^{m,n}\), \(b \in \mathbb{R}^m\), \(c \in \mathbb{R}^n\) and unknown \(x \in \mathbb{R}^{n}\). If some or all variables in the vector \(x\) are restricted over the integers \(\ZZ\), the problem is called mixed integer linear program (MILP). A wide variety of problems in optimization can be formulated in this standard form. Then, solvers are able to calculate a solution.
Example¶
Imagine you want to solve the following linear system of three equations:
\(w_0 + w_1 + w_2 - 14 w_3 = 0\)
\(w_1 + 2 w_2 - 8 w_3 = 0\)
\(2 w_2 - 3 w_3 = 0\)
and this additional inequality:
\(w_0 - w_1 - w_2 \geq 0\)
where all \(w_i \in \ZZ^+\). You know that the trivial solution is \(w_i=0\), but what is the first non-trivial one with \(w_3 \geq 1\)?
A mixed integer linear program can give you an answer:
You have to create an instance of
MixedIntegerLinearProgram
and – in our case – specify that it is a minimization.Create a dictionary
w
of nonnegative integer variablesw
viaw = p.new_variable(integer=True, nonnegative=True)
.Add those three equations as equality constraints via
add_constraint
.Also add the inequality constraint.
Add an inequality constraint \(w_3 \geq 1\) to exclude the trivial solution.
Specify the objective function via
set_objective
. In our case that is just \(w_3\). If it is a pure constraint satisfaction problem, specify it asNone
.To check if everything is set up correctly, you can print the problem via
show
.
Solve
it and print the solution.
The following example shows all these steps:
sage: p = MixedIntegerLinearProgram(maximization=False, solver='GLPK')
sage: w = p.new_variable(integer=True, nonnegative=True)
sage: p.add_constraint(w[0] + w[1] + w[2] - 14*w[3] == 0)
sage: p.add_constraint(w[1] + 2*w[2] - 8*w[3] == 0)
sage: p.add_constraint(2*w[2] - 3*w[3] == 0)
sage: p.add_constraint(w[0] - w[1] - w[2] >= 0)
sage: p.add_constraint(w[3] >= 1)
sage: p.set_objective(w[3])
sage: p.show()
Minimization:
x_3
Constraints:
0.0 <= x_0 + x_1 + x_2 - 14.0 x_3 <= 0.0
0.0 <= x_1 + 2.0 x_2 - 8.0 x_3 <= 0.0
0.0 <= 2.0 x_2 - 3.0 x_3 <= 0.0
- x_0 + x_1 + x_2 <= 0.0
- x_3 <= -1.0
Variables:
x_0 is an integer variable (min=0.0, max=+oo)
x_1 is an integer variable (min=0.0, max=+oo)
x_2 is an integer variable (min=0.0, max=+oo)
x_3 is an integer variable (min=0.0, max=+oo)
sage: print('Objective Value: {}'.format(p.solve()))
Objective Value: 2.0
sage: for i, v in sorted(p.get_values(w, convert=ZZ, tolerance=1e-3).items()):
....: print(f'w_{i} = {v}')
w_0 = 15
w_1 = 10
w_2 = 3
w_3 = 2
>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(maximization=False, solver='GLPK')
>>> w = p.new_variable(integer=True, nonnegative=True)
>>> p.add_constraint(w[Integer(0)] + w[Integer(1)] + w[Integer(2)] - Integer(14)*w[Integer(3)] == Integer(0))
>>> p.add_constraint(w[Integer(1)] + Integer(2)*w[Integer(2)] - Integer(8)*w[Integer(3)] == Integer(0))
>>> p.add_constraint(Integer(2)*w[Integer(2)] - Integer(3)*w[Integer(3)] == Integer(0))
>>> p.add_constraint(w[Integer(0)] - w[Integer(1)] - w[Integer(2)] >= Integer(0))
>>> p.add_constraint(w[Integer(3)] >= Integer(1))
>>> p.set_objective(w[Integer(3)])
>>> p.show()
Minimization:
x_3
Constraints:
0.0 <= x_0 + x_1 + x_2 - 14.0 x_3 <= 0.0
0.0 <= x_1 + 2.0 x_2 - 8.0 x_3 <= 0.0
0.0 <= 2.0 x_2 - 3.0 x_3 <= 0.0
- x_0 + x_1 + x_2 <= 0.0
- x_3 <= -1.0
Variables:
x_0 is an integer variable (min=0.0, max=+oo)
x_1 is an integer variable (min=0.0, max=+oo)
x_2 is an integer variable (min=0.0, max=+oo)
x_3 is an integer variable (min=0.0, max=+oo)
>>> print('Objective Value: {}'.format(p.solve()))
Objective Value: 2.0
>>> for i, v in sorted(p.get_values(w, convert=ZZ, tolerance=RealNumber("1e-3")).items()):
... print(f'w_{i} = {v}')
w_0 = 15
w_1 = 10
w_2 = 3
w_3 = 2
Different backends compute with different base fields, for example:
sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: p.base_ring()
Real Double Field
sage: x = p.new_variable(real=True, nonnegative=True)
sage: 0.5 + 3/2*x[1]
0.5 + 1.5*x_0
sage: p = MixedIntegerLinearProgram(solver='ppl')
sage: p.base_ring()
Rational Field
sage: x = p.new_variable(nonnegative=True)
sage: 0.5 + 3/2*x[1]
1/2 + 3/2*x_0
>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> p.base_ring()
Real Double Field
>>> x = p.new_variable(real=True, nonnegative=True)
>>> RealNumber('0.5') + Integer(3)/Integer(2)*x[Integer(1)]
0.5 + 1.5*x_0
>>> p = MixedIntegerLinearProgram(solver='ppl')
>>> p.base_ring()
Rational Field
>>> x = p.new_variable(nonnegative=True)
>>> RealNumber('0.5') + Integer(3)/Integer(2)*x[Integer(1)]
1/2 + 3/2*x_0
More about MIP variables¶
The underlying MILP backends always work with matrices
where each column corresponds to a linear variable. The
variable corresponding to the \(i\)-th column (counting from 0)
is displayed as x_i
.
MixedIntegerLinearProgram
maintains a dynamic mapping
from the arbitrary keys indexing the components of MIPVariable
objects to the backend variables (indexed by nonnegative integers).
Backend variables are created when a component of a MIPVariable
is accessed.
To make your code more readable, you can construct one or several
MIPVariable
objects that can be arbitrarily named and
indexed. This can be done by calling new_variable()
several times,
or by the following special syntax:
sage: mip.<a,b> = MixedIntegerLinearProgram(solver='GLPK')
sage: a
MIPVariable a with 0 real components
sage: 5 + a[1] + 2*b[3]
5 + x_0 + 2*x_1
>>> from sage.all import *
>>> mip = MixedIntegerLinearProgram(solver='GLPK', names=('a', 'b',)); (a, b,) = mip._first_ngens(2)
>>> a
MIPVariable a with 0 real components
>>> Integer(5) + a[Integer(1)] + Integer(2)*b[Integer(3)]
5 + x_0 + 2*x_1
Indices can be any object, not necessarily integers. Multi-indices are also allowed:
sage: a[4, 'string', QQ]
x_2
sage: a[4, 'string', QQ] - 7*b[2]
x_2 - 7*x_3
sage: mip.show()
Maximization:
Constraints:
Variables:
a[1] = x_0 is a continuous variable (min=-oo, max=+oo)
b[3] = x_1 is a continuous variable (min=-oo, max=+oo)
a[(4, 'string', Rational Field)] = x_2 is a continuous variable (min=-oo, max=+oo)
b[2] = x_3 is a continuous variable (min=-oo, max=+oo)
>>> from sage.all import *
>>> a[Integer(4), 'string', QQ]
x_2
>>> a[Integer(4), 'string', QQ] - Integer(7)*b[Integer(2)]
x_2 - 7*x_3
>>> mip.show()
Maximization:
<BLANKLINE>
Constraints:
Variables:
a[1] = x_0 is a continuous variable (min=-oo, max=+oo)
b[3] = x_1 is a continuous variable (min=-oo, max=+oo)
a[(4, 'string', Rational Field)] = x_2 is a continuous variable (min=-oo, max=+oo)
b[2] = x_3 is a continuous variable (min=-oo, max=+oo)
Upper/lower bounds on a variable can be specified either as separate constraints
(see add_constraint
) or
using the methods set_max
and set_min
respectively.
The default MIP variable¶
As a special shortcut, it is not necessary to call new_variable()
.
A MixedIntegerLinearProgram
has a default MIPVariable
,
whose components are obtained by using the syntax mip[key]
, where
\(key\) is an arbitrary key:
sage: mip = MixedIntegerLinearProgram(solver='GLPK')
sage: 5 + mip[2] + 2*mip[7]
5 + x_0 + 2*x_1
>>> from sage.all import *
>>> mip = MixedIntegerLinearProgram(solver='GLPK')
>>> Integer(5) + mip[Integer(2)] + Integer(2)*mip[Integer(7)]
5 + x_0 + 2*x_1
Index of functions and methods¶
Below are listed the methods of MixedIntegerLinearProgram
. This module
also implements the MIPSolverException
exception, as well as the
MIPVariable
class.
Add a constraint to the |
|
Return the base ring |
|
Return the value of the currently best known bound |
|
Return a list of constraints, as 3-tuples |
|
Return the default |
|
Return the backend instance used |
|
Return the maximum value of a variable |
|
Return the minimum value of a variable |
|
Return the value of the objective function |
|
Return the relative objective gap of the best known solution |
|
Return values found by the previous call to |
|
Test whether the variable |
|
Test whether the variable is an integer |
|
Test whether the variable is real |
|
Return the parent for all linear constraints |
|
Return the parent for all linear functions |
|
Return an instance of |
|
Return the number of constraints assigned so far |
|
Return the number of variables used so far |
|
Return the polyhedron defined by the Linear Program |
|
Remove a constraint from self |
|
Remove several constraints |
|
Set a variable or a |
|
Set a variable or a |
|
Set the maximum value of a variable |
|
Set the minimum value of a variable |
|
Set the objective of the |
|
Set the name of the |
|
Set a variable or a |
|
Display the |
|
Solve the |
|
Return or define a solver parameter |
|
Efficiently computes the sum of a sequence of LinearFunction elements |
|
Write the linear program as a LP file |
|
Write the linear program as a MPS file |
AUTHORS:
Risan (2012/02): added extension for exact computation
- exception sage.numerical.mip.MIPSolverException[source]¶
Bases:
RuntimeError
Exception raised when the solver fails.
EXAMPLES:
sage: from sage.numerical.mip import MIPSolverException sage: e = MIPSolverException("Error") sage: e MIPSolverException('Error'...) sage: print(e) Error
>>> from sage.all import * >>> from sage.numerical.mip import MIPSolverException >>> e = MIPSolverException("Error") >>> e MIPSolverException('Error'...) >>> print(e) Error
- class sage.numerical.mip.MIPVariable[source]¶
Bases:
FiniteFamily
MIPVariable
is a variable used by the classMixedIntegerLinearProgram
.Warning
You should not instantiate this class directly. Instead, use
MixedIntegerLinearProgram.new_variable()
.- copy_for_mip(mip)[source]¶
Return a copy of
self
suitable for a newMixedIntegerLinearProgram
instancemip
.For this to make sense,
mip
should have been obtained as a copy ofself.mip()
.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: pv = p.new_variable(nonnegative=True) sage: pv[0] x_0 sage: q = copy(p) sage: qv = pv.copy_for_mip(q) sage: pv[77] x_1 sage: p.number_of_variables() 2 sage: q.number_of_variables() 1 sage: qv[33] x_1 sage: p.number_of_variables() 2 sage: q.number_of_variables() 2 sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: pv = p.new_variable(indices=[3, 7]) sage: q = copy(p) sage: qv = pv.copy_for_mip(q) sage: qv[3] x_0 sage: qv[5] Traceback (most recent call last): ... IndexError: 5 does not index a component of MIPVariable with 2 real components
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> pv = p.new_variable(nonnegative=True) >>> pv[Integer(0)] x_0 >>> q = copy(p) >>> qv = pv.copy_for_mip(q) >>> pv[Integer(77)] x_1 >>> p.number_of_variables() 2 >>> q.number_of_variables() 1 >>> qv[Integer(33)] x_1 >>> p.number_of_variables() 2 >>> q.number_of_variables() 2 >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> pv = p.new_variable(indices=[Integer(3), Integer(7)]) >>> q = copy(p) >>> qv = pv.copy_for_mip(q) >>> qv[Integer(3)] x_0 >>> qv[Integer(5)] Traceback (most recent call last): ... IndexError: 5 does not index a component of MIPVariable with 2 real components
- items()[source]¶
Return the pairs (keys, value) contained in the dictionary.
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.set_objective(v[0] + v[1]) sage: sorted(v.items()) [(0, x_0), (1, x_1)]
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.set_objective(v[Integer(0)] + v[Integer(1)]) >>> sorted(v.items()) [(0, x_0), (1, x_1)]
- keys()[source]¶
Return the keys already defined in the dictionary.
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.set_objective(v[0] + v[1]) sage: sorted(v.keys()) [0, 1]
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.set_objective(v[Integer(0)] + v[Integer(1)]) >>> sorted(v.keys()) [0, 1]
- mip()[source]¶
Return the
MixedIntegerLinearProgram
in whichself
is a variable.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p == v.mip() True
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p == v.mip() True
- set_max(max)[source]¶
Set an upper bound on the variable.
INPUT:
max
– an upper bound, orNone
to mean that the variable is unbounded
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(real=True, nonnegative=True) sage: p.get_max(v) sage: p.get_max(v[0]) sage: p.set_max(v,4) sage: p.get_max(v) 4 sage: p.get_max(v[0]) 4.0
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(real=True, nonnegative=True) >>> p.get_max(v) >>> p.get_max(v[Integer(0)]) >>> p.set_max(v,Integer(4)) >>> p.get_max(v) 4 >>> p.get_max(v[Integer(0)]) 4.0
- set_min(min)[source]¶
Set a lower bound on the variable.
INPUT:
min
– a lower bound, orNone
to mean that the variable is unbounded
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(real=True, nonnegative=True) sage: p.get_min(v) 0 sage: p.get_min(v[0]) 0.0 sage: p.set_min(v,4) sage: p.get_min(v) 4 sage: p.get_min(v[0]) 4.0
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(real=True, nonnegative=True) >>> p.get_min(v) 0 >>> p.get_min(v[Integer(0)]) 0.0 >>> p.set_min(v,Integer(4)) >>> p.get_min(v) 4 >>> p.get_min(v[Integer(0)]) 4.0
- values()[source]¶
Return the symbolic variables associated to the current dictionary.
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.set_objective(v[0] + v[1]) sage: sorted(v.values(), key=str) [x_0, x_1]
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.set_objective(v[Integer(0)] + v[Integer(1)]) >>> sorted(v.values(), key=str) [x_0, x_1]
- class sage.numerical.mip.MixedIntegerLinearProgram[source]¶
Bases:
SageObject
The
MixedIntegerLinearProgram
class is the link between Sage, linear programming (LP) and mixed integer programming (MIP) solvers.A Mixed Integer Linear Program (MILP) consists of variables, linear constraints on these variables, and an objective function which is to be maximised or minimised under these constraints.
See the thematic tutorial on Linear Programming (Mixed Integer) or Wikipedia article Linear_programming for further information on linear programming, and the
MILP module
for its use in Sage.INPUT:
solver
– selects a solver; see Solvers (backends) for more information and installation instructions for optional solvers.solver="GLPK"
: the GNU Linear Programming Kit.solver="GLPK/exact"
: GLPK’s implementation of an exact rational simplex method.solver="Coin"
: the COIN-OR CBC (COIN Branch and Cut) solver.solver="CPLEX"
: provided by the proprietary IBM ILOG CPLEX Optimization Studio.solver="Gurobi"
: the proprietary Gurobi solver.solver="CVXOPT"
: see the CVXOPT web site.solver="PPL"
: an exact rational solver (for small scale instances) provided by the Parma Polyhedra Library (PPL).solver="InteractiveLP"
: a didactical implementation of the revised simplex method in Sage. It works over any exact ordered field, the default isQQ
.If
solver=None
(default), the default solver is used (seedefault_mip_solver()
).solver
can also be a callable (such as a class), seesage.numerical.backends.generic_backend.get_solver()
for examples.
maximization
When set to
True
(default), theMixedIntegerLinearProgram
is defined as a maximization.When set to
False
, theMixedIntegerLinearProgram
is defined as a minimization.
constraint_generation
– only used whensolver=None
When set to
True
, after solving theMixedIntegerLinearProgram
, it is possible to add a constraint, and then solve it again. The effect is that solvers that do not support this feature will not be used.Defaults to
False
.
See also
default_mip_solver()
– returns/sets the default MIP solver
EXAMPLES:
Computation of a maximum stable set in Petersen’s graph:
sage: # needs sage.graphs sage: g = graphs.PetersenGraph() sage: p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') sage: b = p.new_variable(binary=True) sage: p.set_objective(sum([b[v] for v in g])) sage: for (u,v) in g.edges(sort=False, labels=None): ....: p.add_constraint(b[u] + b[v], max=1) sage: p.solve(objective_only=True) 4.0
>>> from sage.all import * >>> # needs sage.graphs >>> g = graphs.PetersenGraph() >>> p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') >>> b = p.new_variable(binary=True) >>> p.set_objective(sum([b[v] for v in g])) >>> for (u,v) in g.edges(sort=False, labels=None): ... p.add_constraint(b[u] + b[v], max=Integer(1)) >>> p.solve(objective_only=True) 4.0
- add_constraint(linear_function, max=None, min=None, name=None, return_indices=False)[source]¶
Add a constraint to the
MixedIntegerLinearProgram
.INPUT:
linear_function
– four different types of arguments are admissible:A linear function. In this case, one of the arguments
min
ormax
has to be specified.A linear constraint of the form
A <= B
,A >= B
,A <= B <= C
,A >= B >= C
orA == B
.A vector-valued linear function, see
linear_tensor
. In this case, one of the argumentsmin
ormax
has to be specified.An (in)equality of vector-valued linear functions, that is, elements of the space of linear functions tensored with a vector space. See
linear_tensor_constraints
for details.
max
– constant orNone
(default). An upper bound on the linear function. This must be a numerical value for scalar linear functions, or a vector for vector-valued linear functions. Not allowed if thelinear_function
argument is a symbolic (in)-equality.min
– constant orNone
(default). A lower bound on the linear function. This must be a numerical value for scalar linear functions, or a vector for vector-valued linear functions. Not allowed if thelinear_function
argument is a symbolic (in)-equality.name
– a name for the constraintreturn_indices
– boolean (default:False
), whether to return the indices of the added constraints
OUTPUT:
The row indices of the constraints added, if
return_indices
is true and the backend guarantees that removing them again yields the original MIP,None
otherwise.To set a lower and/or upper bound on the variables use the methods
set_min
and/orset_max
ofMixedIntegerLinearProgram
.EXAMPLES:
Consider the following linear program:
Maximize: x + 5 * y Constraints: x + 0.2 y <= 4 1.5 * x + 3 * y <= 4 Variables: x is Real (min = 0, max = None) y is Real (min = 0, max = None)
It can be solved as follows:
sage: p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[0] + 5*x[1]) sage: p.add_constraint(x[0] + 0.2*x[1], max=4) sage: p.add_constraint(1.5*x[0] + 3*x[1], max=4) sage: p.solve() # rel tol 1e-15 6.666666666666666
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(0)] + Integer(5)*x[Integer(1)]) >>> p.add_constraint(x[Integer(0)] + RealNumber('0.2')*x[Integer(1)], max=Integer(4)) >>> p.add_constraint(RealNumber('1.5')*x[Integer(0)] + Integer(3)*x[Integer(1)], max=Integer(4)) >>> p.solve() # rel tol 1e-15 6.666666666666666
There are two different ways to add the constraint
x[5] + 3*x[7] <= x[6] + 3
to aMixedIntegerLinearProgram
.The first one consists in giving
add_constraint
this very expression:sage: p.add_constraint(x[5] + 3*x[7] <= x[6] + 3)
>>> from sage.all import * >>> p.add_constraint(x[Integer(5)] + Integer(3)*x[Integer(7)] <= x[Integer(6)] + Integer(3))
The second (slightly more efficient) one is to use the arguments
min
ormax
, which can only be numerical values:sage: p.add_constraint(x[5] + 3*x[7] - x[6], max=3)
>>> from sage.all import * >>> p.add_constraint(x[Integer(5)] + Integer(3)*x[Integer(7)] - x[Integer(6)], max=Integer(3))
One can also define double-bounds or equality using symbols
<=
,>=
and==
:sage: p.add_constraint(x[5] + 3*x[7] == x[6] + 3) sage: p.add_constraint(x[5] + 3*x[7] <= x[6] + 3 <= x[8] + 27)
>>> from sage.all import * >>> p.add_constraint(x[Integer(5)] + Integer(3)*x[Integer(7)] == x[Integer(6)] + Integer(3)) >>> p.add_constraint(x[Integer(5)] + Integer(3)*x[Integer(7)] <= x[Integer(6)] + Integer(3) <= x[Integer(8)] + Integer(27))
Using this notation, the previous program can be written as:
sage: p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[0] + 5*x[1]) sage: p.add_constraint(x[0] + 0.2*x[1] <= 4) sage: p.add_constraint(1.5*x[0] + 3*x[1] <= 4) sage: p.solve() # rel tol 1e-15 6.666666666666666
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(0)] + Integer(5)*x[Integer(1)]) >>> p.add_constraint(x[Integer(0)] + RealNumber('0.2')*x[Integer(1)] <= Integer(4)) >>> p.add_constraint(RealNumber('1.5')*x[Integer(0)] + Integer(3)*x[Integer(1)] <= Integer(4)) >>> p.solve() # rel tol 1e-15 6.666666666666666
The two constraints can also be combined into a single vector-valued constraint:
sage: p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[0] + 5*x[1]) sage: f_vec = vector([1, 1.5]) * x[0] + vector([0.2, 3]) * x[1]; f_vec (1.0, 1.5)*x_0 + (0.2, 3.0)*x_1 sage: p.add_constraint(f_vec, max=vector([4, 4])) sage: p.solve() # rel tol 1e-15 6.666666666666666
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(0)] + Integer(5)*x[Integer(1)]) >>> f_vec = vector([Integer(1), RealNumber('1.5')]) * x[Integer(0)] + vector([RealNumber('0.2'), Integer(3)]) * x[Integer(1)]; f_vec (1.0, 1.5)*x_0 + (0.2, 3.0)*x_1 >>> p.add_constraint(f_vec, max=vector([Integer(4), Integer(4)])) >>> p.solve() # rel tol 1e-15 6.666666666666666
Instead of specifying the maximum in the optional
max
argument, we can also use (in)equality notation for vector-valued linear functions:sage: f_vec <= 4 # constant rhs becomes vector (1.0, 1.5)*x_0 + (0.2, 3.0)*x_1 <= (4.0, 4.0) sage: p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[0] + 5*x[1]) sage: p.add_constraint(f_vec <= 4) sage: p.solve() # rel tol 1e-15 6.666666666666666
>>> from sage.all import * >>> f_vec <= Integer(4) # constant rhs becomes vector (1.0, 1.5)*x_0 + (0.2, 3.0)*x_1 <= (4.0, 4.0) >>> p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(0)] + Integer(5)*x[Integer(1)]) >>> p.add_constraint(f_vec <= Integer(4)) >>> p.solve() # rel tol 1e-15 6.666666666666666
Finally, one can use the matrix *
MIPVariable
notation to write vector-valued linear functions:sage: m = matrix([[1.0, 0.2], [1.5, 3.0]]); m [ 1.00000000000000 0.200000000000000] [ 1.50000000000000 3.00000000000000] sage: p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[0] + 5*x[1]) sage: p.add_constraint(m * x <= 4) sage: p.solve() # rel tol 1e-15 6.666666666666666
>>> from sage.all import * >>> m = matrix([[RealNumber('1.0'), RealNumber('0.2')], [RealNumber('1.5'), RealNumber('3.0')]]); m [ 1.00000000000000 0.200000000000000] [ 1.50000000000000 3.00000000000000] >>> p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(0)] + Integer(5)*x[Integer(1)]) >>> p.add_constraint(m * x <= Integer(4)) >>> p.solve() # rel tol 1e-15 6.666666666666666
- base_ring()[source]¶
Return the base ring.
OUTPUT: a ring. The coefficients that the chosen solver supports
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.base_ring() Real Double Field sage: p = MixedIntegerLinearProgram(solver='ppl') sage: p.base_ring() Rational Field sage: from sage.rings.qqbar import AA # needs sage.rings.number_field sage: p = MixedIntegerLinearProgram(solver='InteractiveLP', base_ring=AA) # needs sage.rings.number_field sage: p.base_ring() # needs sage.rings.number_field Algebraic Real Field sage: # needs sage.groups sage.rings.number_field sage: d = polytopes.dodecahedron() sage: p = MixedIntegerLinearProgram(base_ring=d.base_ring()) sage: p.base_ring() Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.base_ring() Real Double Field >>> p = MixedIntegerLinearProgram(solver='ppl') >>> p.base_ring() Rational Field >>> from sage.rings.qqbar import AA # needs sage.rings.number_field >>> p = MixedIntegerLinearProgram(solver='InteractiveLP', base_ring=AA) # needs sage.rings.number_field >>> p.base_ring() # needs sage.rings.number_field Algebraic Real Field >>> # needs sage.groups sage.rings.number_field >>> d = polytopes.dodecahedron() >>> p = MixedIntegerLinearProgram(base_ring=d.base_ring()) >>> p.base_ring() Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?
- best_known_objective_bound()[source]¶
Return the value of the currently best known bound.
This method returns the current best upper (resp. lower) bound on the optimal value of the objective function in a maximization (resp. minimization) problem. It is equal to the output of
get_objective_value()
if the MILP found an optimal solution, but it can differ if it was interrupted manually or after a time limit (cfsolver_parameter()
).Note
Has no meaning unless
solve
has been called before.EXAMPLES:
sage: # needs sage.graphs sage: g = graphs.CubeGraph(9) sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.solver_parameter("mip_gap_tolerance",100) sage: b = p.new_variable(binary=True) sage: p.set_objective(p.sum(b[v] for v in g)) sage: for v in g: ....: p.add_constraint(b[v] + p.sum(b[u] for u in g.neighbors(v)) <= 1) sage: p.add_constraint(b[v] == 1) # Force an easy non-0 solution sage: p.solve() # rel tol 100 1.0 sage: p.best_known_objective_bound() # random 48.0
>>> from sage.all import * >>> # needs sage.graphs >>> g = graphs.CubeGraph(Integer(9)) >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.solver_parameter("mip_gap_tolerance",Integer(100)) >>> b = p.new_variable(binary=True) >>> p.set_objective(p.sum(b[v] for v in g)) >>> for v in g: ... p.add_constraint(b[v] + p.sum(b[u] for u in g.neighbors(v)) <= Integer(1)) >>> p.add_constraint(b[v] == Integer(1)) # Force an easy non-0 solution >>> p.solve() # rel tol 100 1.0 >>> p.best_known_objective_bound() # random 48.0
- constraints(indices=None)[source]¶
Return a list of constraints, as 3-tuples.
INPUT:
indices
– select which constraint(s) to returnIf
indices = None
, the method returns the list of all the constraints.If
indices
is an integer \(i\), the method returns constraint \(i\).If
indices
is a list of integers, the method returns the list of the corresponding constraints.
OUTPUT:
Each constraint is returned as a triple
lower_bound, (indices, coefficients), upper_bound
. For each of those entries, the corresponding linear function is the one associating to variableindices[i]
the coefficientcoefficients[i]
, and \(0\) to all the others.lower_bound
andupper_bound
are numerical values.EXAMPLES:
First, let us define a small LP:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.add_constraint(p[0] - p[2], min=1, max=4) sage: p.add_constraint(p[0] - 2*p[1], min=1)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.add_constraint(p[Integer(0)] - p[Integer(2)], min=Integer(1), max=Integer(4)) >>> p.add_constraint(p[Integer(0)] - Integer(2)*p[Integer(1)], min=Integer(1))
To obtain the list of all constraints:
sage: p.constraints() # not tested [(1.0, ([1, 0], [-1.0, 1.0]), 4.0), (1.0, ([2, 0], [-2.0, 1.0]), None)]
>>> from sage.all import * >>> p.constraints() # not tested [(1.0, ([1, 0], [-1.0, 1.0]), 4.0), (1.0, ([2, 0], [-2.0, 1.0]), None)]
Or constraint \(0\) only:
sage: p.constraints(0) # not tested (1.0, ([1, 0], [-1.0, 1.0]), 4.0)
>>> from sage.all import * >>> p.constraints(Integer(0)) # not tested (1.0, ([1, 0], [-1.0, 1.0]), 4.0)
A list of constraints containing only \(1\):
sage: p.constraints([1]) # not tested [(1.0, ([2, 0], [-2.0, 1.0]), None)]
>>> from sage.all import * >>> p.constraints([Integer(1)]) # not tested [(1.0, ([2, 0], [-2.0, 1.0]), None)]
- default_variable()[source]¶
Return the default
MIPVariable
ofself
.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.default_variable() MIPVariable with 0 real components
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.default_variable() MIPVariable with 0 real components
- get_backend()[source]¶
Return the backend instance used.
This might be useful when access to additional functions provided by the backend is needed.
EXAMPLES:
This example uses the simplex algorithm and prints information:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x, y = p[0], p[1] sage: p.add_constraint(2*x + 3*y, max=6) sage: p.add_constraint(3*x + 2*y, max=6) sage: p.set_objective(x + y + 7) sage: b = p.get_backend() sage: b.solver_parameter("simplex_or_intopt", "simplex_only") sage: b.solver_parameter("verbosity_simplex", "GLP_MSG_ALL") sage: ans = p.solve() GLPK Simplex Optimizer... 2 rows, 2 columns, 4 non-zeros * 0: obj = 7.000000000e+00 inf = 0.000e+00 (2) * 2: obj = 9.400000000e+00 inf = 0.000e+00 (0) OPTIMAL LP SOLUTION FOUND sage: ans # rel tol 1e-5 9.4
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x, y = p[Integer(0)], p[Integer(1)] >>> p.add_constraint(Integer(2)*x + Integer(3)*y, max=Integer(6)) >>> p.add_constraint(Integer(3)*x + Integer(2)*y, max=Integer(6)) >>> p.set_objective(x + y + Integer(7)) >>> b = p.get_backend() >>> b.solver_parameter("simplex_or_intopt", "simplex_only") >>> b.solver_parameter("verbosity_simplex", "GLP_MSG_ALL") >>> ans = p.solve() GLPK Simplex Optimizer... 2 rows, 2 columns, 4 non-zeros * 0: obj = 7.000000000e+00 inf = 0.000e+00 (2) * 2: obj = 9.400000000e+00 inf = 0.000e+00 (0) OPTIMAL LP SOLUTION FOUND >>> ans # rel tol 1e-5 9.4
- get_max(v)[source]¶
Return the maximum value of a variable.
INPUT:
v
– a variable
OUTPUT:
Maximum value of the variable, or
None
if the variable has no upper bound.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.set_objective(v[1]) sage: p.get_max(v[1]) sage: p.set_max(v[1],6) sage: p.get_max(v[1]) 6.0
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.set_objective(v[Integer(1)]) >>> p.get_max(v[Integer(1)]) >>> p.set_max(v[Integer(1)],Integer(6)) >>> p.get_max(v[Integer(1)]) 6.0
- get_min(v)[source]¶
Return the minimum value of a variable.
INPUT:
v
– a variable
OUTPUT:
Minimum value of the variable, or
None
if the variable has no lower bound.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.set_objective(v[1]) sage: p.get_min(v[1]) 0.0 sage: p.set_min(v[1],6) sage: p.get_min(v[1]) 6.0 sage: p.set_min(v[1], None) sage: p.get_min(v[1])
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.set_objective(v[Integer(1)]) >>> p.get_min(v[Integer(1)]) 0.0 >>> p.set_min(v[Integer(1)],Integer(6)) >>> p.get_min(v[Integer(1)]) 6.0 >>> p.set_min(v[Integer(1)], None) >>> p.get_min(v[Integer(1)])
- get_objective_value()[source]¶
Return the value of the objective function.
Note
Behaviour is undefined unless
solve
has been called before.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x, y = p[0], p[1] sage: p.add_constraint(2*x + 3*y, max=6) sage: p.add_constraint(3*x + 2*y, max=6) sage: p.set_objective(x + y + 7) sage: p.solve() # rel tol 1e-5 9.4 sage: p.get_objective_value() # rel tol 1e-5 9.4
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x, y = p[Integer(0)], p[Integer(1)] >>> p.add_constraint(Integer(2)*x + Integer(3)*y, max=Integer(6)) >>> p.add_constraint(Integer(3)*x + Integer(2)*y, max=Integer(6)) >>> p.set_objective(x + y + Integer(7)) >>> p.solve() # rel tol 1e-5 9.4 >>> p.get_objective_value() # rel tol 1e-5 9.4
- get_relative_objective_gap()[source]¶
Return the relative objective gap of the best known solution.
For a minimization problem, this value is computed by \((\texttt{bestinteger} - \texttt{bestobjective}) / (1e-10 + |\texttt{bestobjective}|)\), where
bestinteger
is the value returned byget_objective_value()
andbestobjective
is the value returned bybest_known_objective_bound()
. For a maximization problem, the value is computed by \((\texttt{bestobjective} - \texttt{bestinteger}) / (1e-10 + |\texttt{bestobjective}|)\).Note
Has no meaning unless
solve
has been called before.EXAMPLES:
sage: # needs sage.graphs sage: g = graphs.CubeGraph(9) sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.solver_parameter("mip_gap_tolerance",100) sage: b = p.new_variable(binary=True) sage: p.set_objective(p.sum(b[v] for v in g)) sage: for v in g: ....: p.add_constraint(b[v] + p.sum(b[u] for u in g.neighbors(v)) <= 1) sage: p.add_constraint(b[v] == 1) # Force an easy non-0 solution sage: p.solve() # rel tol 100 1.0 sage: p.get_relative_objective_gap() # random 46.99999999999999
>>> from sage.all import * >>> # needs sage.graphs >>> g = graphs.CubeGraph(Integer(9)) >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.solver_parameter("mip_gap_tolerance",Integer(100)) >>> b = p.new_variable(binary=True) >>> p.set_objective(p.sum(b[v] for v in g)) >>> for v in g: ... p.add_constraint(b[v] + p.sum(b[u] for u in g.neighbors(v)) <= Integer(1)) >>> p.add_constraint(b[v] == Integer(1)) # Force an easy non-0 solution >>> p.solve() # rel tol 100 1.0 >>> p.get_relative_objective_gap() # random 46.99999999999999
- get_values(convert=None, tolerance=None, *lists)[source]¶
Return values found by the previous call to
solve()
.INPUT:
*lists
– any instance ofMIPVariable
(or one of its elements), or lists of themconvert
– (default:None
)ZZ
,bool
, orTrue
:if
convert=None
(default), return all variable values as the backend provides them, i.e., as an element ofbase_ring()
or afloat
.if
convert=ZZ
, convert all variable values from thebase_ring()
by rounding to the nearest integer.if
convert=bool
, convert all variable values from thebase_ring()
by rounding to 0/1 and converting tobool
.if
convert=True
, useZZ
for MIP variables declared integer or binary, and convert the values of all other variables to thebase_ring()
.
tolerance
–None
, a positive real number, or0
(ifbase_ring()
is an exact ring). Required ifconvert
is notNone
and any integer conversion is to be done. If the variable value differs from the nearest integer by more thantolerance
, raise aRuntimeError
.
OUTPUT:
Each instance of
MIPVariable
is replaced by a dictionary containing the numerical values found for each corresponding variable in the instance.Each element of an instance of a
MIPVariable
is replaced by its corresponding numerical value.
Note
While a variable may be declared as binary or integer, its value is an element of the
base_ring()
, or for the numerical solvers, afloat
.For the numerical solvers,
base_ring()
isRDF
, an inexact ring. Code usingget_values
should always account for possible numerical errors.Even for variables declared as binary or integer, or known to be an integer because of the mathematical properties of the model, the returned values cannot be expected to be exact integers. This is normal behavior of the numerical solvers.
For correct operation, any user code needs to avoid exact comparisons (
==
,!=
) and instead allow for numerical tolerances. The magnitude of the numerical tolerances depends on both the model and the solver.The arguments
convert
andtolerance
facilitate writing correct code. See examples below.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: y = p.new_variable(nonnegative=True) sage: p.set_objective(x[3] + 3*y[2,9] + x[5]) sage: p.add_constraint(x[3] + y[2,9] + 2*x[5], max=2) sage: p.solve() 6.0
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> y = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(3)] + Integer(3)*y[Integer(2),Integer(9)] + x[Integer(5)]) >>> p.add_constraint(x[Integer(3)] + y[Integer(2),Integer(9)] + Integer(2)*x[Integer(5)], max=Integer(2)) >>> p.solve() 6.0
To return the value of
y[2,9]
in the optimal solution:sage: p.get_values(y[2,9]) 2.0 sage: type(_) <class 'float'>
>>> from sage.all import * >>> p.get_values(y[Integer(2),Integer(9)]) 2.0 >>> type(_) <class 'float'>
To convert the value to the
base_ring()
:sage: p.get_values(y[2,9], convert=True) 2.0 sage: _.parent() Real Double Field
>>> from sage.all import * >>> p.get_values(y[Integer(2),Integer(9)], convert=True) 2.0 >>> _.parent() Real Double Field
To get a dictionary identical to
x
containing the values for the corresponding variables in the optimal solution:sage: x_sol = p.get_values(x) sage: sorted(x_sol) [3, 5]
>>> from sage.all import * >>> x_sol = p.get_values(x) >>> sorted(x_sol) [3, 5]
Obviously, it also works with variables of higher dimension:
sage: y_sol = p.get_values(y)
>>> from sage.all import * >>> y_sol = p.get_values(y)
We could also have tried
sage: [x_sol, y_sol] = p.get_values(x, y)
>>> from sage.all import * >>> [x_sol, y_sol] = p.get_values(x, y)
Or:
sage: [x_sol, y_sol] = p.get_values([x, y])
>>> from sage.all import * >>> [x_sol, y_sol] = p.get_values([x, y])
Using
convert
andtolerance
. First, a binary knapsack:sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(binary=True) sage: p.set_objective(3*x[1] + 4*x[2] + 5*x[3]) sage: p.add_constraint(2*x[1] + 3*x[2] + 4*x[3] <= 6) sage: p.solve() 8.0 sage: x_opt = p.get_values(x); x_opt {1: 1.0, 2: 0.0, 3: 1.0} sage: type(x_opt[1]) <class 'float'> sage: x_opt_ZZ = p.get_values(x, convert=True, tolerance=1e-6); x_opt_ZZ {1: 1, 2: 0, 3: 1} sage: x_opt_ZZ[1].parent() Integer Ring sage: x_opt_bool = p.get_values(x, convert=bool, tolerance=1e-6); x_opt_bool {1: True, 2: False, 3: True}
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(binary=True) >>> p.set_objective(Integer(3)*x[Integer(1)] + Integer(4)*x[Integer(2)] + Integer(5)*x[Integer(3)]) >>> p.add_constraint(Integer(2)*x[Integer(1)] + Integer(3)*x[Integer(2)] + Integer(4)*x[Integer(3)] <= Integer(6)) >>> p.solve() 8.0 >>> x_opt = p.get_values(x); x_opt {1: 1.0, 2: 0.0, 3: 1.0} >>> type(x_opt[Integer(1)]) <class 'float'> >>> x_opt_ZZ = p.get_values(x, convert=True, tolerance=RealNumber('1e-6')); x_opt_ZZ {1: 1, 2: 0, 3: 1} >>> x_opt_ZZ[Integer(1)].parent() Integer Ring >>> x_opt_bool = p.get_values(x, convert=bool, tolerance=RealNumber('1e-6')); x_opt_bool {1: True, 2: False, 3: True}
Thanks to total unimodularity, single-commodity network flow problems with integer capacities and integer supplies/demands have integer vertex solutions. Hence the integrality of solutions is mathematically guaranteed in an optimal solution if we use the simplex algorithm. A numerical LP solver based on the simplex method such as GLPK will return an integer solution only up to a numerical error. Hence, for correct operation, we should use
tolerance
:sage: p = MixedIntegerLinearProgram(solver='GLPK', maximization=False) sage: x = p.new_variable(nonnegative=True) sage: x.set_max(1) sage: p.add_constraint(x['sa'] + x['sb'] == 1) sage: p.add_constraint(x['sa'] + x['ba'] - x['ab'] - x['at'] == 0) sage: p.add_constraint(x['sb'] + x['ab'] - x['ba'] - x['bt'] == 0) sage: p.set_objective(10*x['sa'] + 10*x['bt']) sage: p.solve() 0.0 sage: x_opt = p.get_values(x); x_opt {'ab': 0.0, 'at': 1.0, 'ba': 1.0, 'bt': -0.0, 'sa': 0.0, 'sb': 1.0} sage: x_opt_ZZ = p.get_values(x, convert=ZZ, tolerance=1e-6); x_opt_ZZ {'ab': 0, 'at': 1, 'ba': 1, 'bt': 0, 'sa': 0, 'sb': 1}
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK', maximization=False) >>> x = p.new_variable(nonnegative=True) >>> x.set_max(Integer(1)) >>> p.add_constraint(x['sa'] + x['sb'] == Integer(1)) >>> p.add_constraint(x['sa'] + x['ba'] - x['ab'] - x['at'] == Integer(0)) >>> p.add_constraint(x['sb'] + x['ab'] - x['ba'] - x['bt'] == Integer(0)) >>> p.set_objective(Integer(10)*x['sa'] + Integer(10)*x['bt']) >>> p.solve() 0.0 >>> x_opt = p.get_values(x); x_opt {'ab': 0.0, 'at': 1.0, 'ba': 1.0, 'bt': -0.0, 'sa': 0.0, 'sb': 1.0} >>> x_opt_ZZ = p.get_values(x, convert=ZZ, tolerance=RealNumber('1e-6')); x_opt_ZZ {'ab': 0, 'at': 1, 'ba': 1, 'bt': 0, 'sa': 0, 'sb': 1}
- interactive_lp_problem(form='standard')[source]¶
Return an InteractiveLPProblem and, if available, a basis.
INPUT:
form
– (default:'standard'
) a string specifying return type: eitherNone
, or'std'
or'standard'
, respectively returns an instance ofInteractiveLPProblem
or ofInteractiveLPProblemStandardForm
OUTPUT:
A 2-tuple consists of an instance of class
InteractiveLPProblem
orInteractiveLPProblemStandardForm
that is constructed based on a givenMixedIntegerLinearProgram
, and a list of basic variables (the basis) if standard form is chosen (by default), otherwiseNone
.All variables must have 0 as lower bound and no upper bound.
EXAMPLES:
sage: p = MixedIntegerLinearProgram(names=['m'], solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: y = p.new_variable(nonnegative=True, name='n') sage: v = p.new_variable(nonnegative=True) sage: p.add_constraint(x[0] + x[1] - 7*y[0] + v[0] <= 2, name='K') sage: p.add_constraint(x[1] + 2*y[0] - v[0] <= 3) sage: p.add_constraint(5*x[0] + y[0] <= 21, name='L') sage: p.set_objective(2*x[0] + 3*x[1] + 4*y[0] + 5*v[0]) sage: lp, basis = p.interactive_lp_problem() sage: basis ['K', 'w_1', 'L'] sage: lp.constraint_coefficients() [ 1.0 1.0 -7.0 1.0] [ 0.0 1.0 2.0 -1.0] [ 5.0 0.0 1.0 0.0] sage: lp.b() (2.0, 3.0, 21.0) sage: lp.objective_coefficients() (2.0, 3.0, 4.0, 5.0) sage: lp.decision_variables() (m_0, m_1, n_0, x_3) sage: view(lp) #not tested sage: d = lp.dictionary(*basis) sage: view(d) #not tested
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(names=['m'], solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> y = p.new_variable(nonnegative=True, name='n') >>> v = p.new_variable(nonnegative=True) >>> p.add_constraint(x[Integer(0)] + x[Integer(1)] - Integer(7)*y[Integer(0)] + v[Integer(0)] <= Integer(2), name='K') >>> p.add_constraint(x[Integer(1)] + Integer(2)*y[Integer(0)] - v[Integer(0)] <= Integer(3)) >>> p.add_constraint(Integer(5)*x[Integer(0)] + y[Integer(0)] <= Integer(21), name='L') >>> p.set_objective(Integer(2)*x[Integer(0)] + Integer(3)*x[Integer(1)] + Integer(4)*y[Integer(0)] + Integer(5)*v[Integer(0)]) >>> lp, basis = p.interactive_lp_problem() >>> basis ['K', 'w_1', 'L'] >>> lp.constraint_coefficients() [ 1.0 1.0 -7.0 1.0] [ 0.0 1.0 2.0 -1.0] [ 5.0 0.0 1.0 0.0] >>> lp.b() (2.0, 3.0, 21.0) >>> lp.objective_coefficients() (2.0, 3.0, 4.0, 5.0) >>> lp.decision_variables() (m_0, m_1, n_0, x_3) >>> view(lp) #not tested >>> d = lp.dictionary(*basis) >>> view(d) #not tested
- is_binary(e)[source]¶
Test whether the variable
e
is binary. Variables are real by default.INPUT:
e
– a variable (not aMIPVariable
, but one of its elements)
OUTPUT:
True
if the variablee
is binary;False
otherwiseEXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.set_objective(v[1]) sage: p.is_binary(v[1]) False sage: p.set_binary(v[1]) sage: p.is_binary(v[1]) True
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.set_objective(v[Integer(1)]) >>> p.is_binary(v[Integer(1)]) False >>> p.set_binary(v[Integer(1)]) >>> p.is_binary(v[Integer(1)]) True
- is_integer(e)[source]¶
Test whether the variable is an integer. Variables are real by default.
INPUT:
e
– a variable (not aMIPVariable
, but one of its elements)
OUTPUT:
True
if the variablee
is an integer;False
otherwiseEXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.set_objective(v[1]) sage: p.is_integer(v[1]) False sage: p.set_integer(v[1]) sage: p.is_integer(v[1]) True
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.set_objective(v[Integer(1)]) >>> p.is_integer(v[Integer(1)]) False >>> p.set_integer(v[Integer(1)]) >>> p.is_integer(v[Integer(1)]) True
- is_real(e)[source]¶
Test whether the variable is real.
INPUT:
e
– a variable (not aMIPVariable
, but one of its elements)
OUTPUT:
True
if the variable is real;False
otherwiseEXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.set_objective(v[1]) sage: p.is_real(v[1]) True sage: p.set_binary(v[1]) sage: p.is_real(v[1]) False sage: p.set_real(v[1]) sage: p.is_real(v[1]) True
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.set_objective(v[Integer(1)]) >>> p.is_real(v[Integer(1)]) True >>> p.set_binary(v[Integer(1)]) >>> p.is_real(v[Integer(1)]) False >>> p.set_real(v[Integer(1)]) >>> p.is_real(v[Integer(1)]) True
- linear_constraints_parent()[source]¶
Return the parent for all linear constraints.
See
linear_functions
for more details.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.linear_constraints_parent() Linear constraints over Real Double Field
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.linear_constraints_parent() Linear constraints over Real Double Field
- linear_functions_parent()[source]¶
Return the parent for all linear functions.
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.linear_functions_parent() Linear functions over Real Double Field
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.linear_functions_parent() Linear functions over Real Double Field
- new_variable(real=False, binary=False, integer=False, nonnegative=False, name='', indices=None)[source]¶
Return a new
MIPVariable
instance.A new variable
x
is defined by:sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(nonnegative=True)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(nonnegative=True)
It behaves exactly as a usual dictionary would. It can use any key argument you may like, as
x[5]
orx["b"]
, and has methodsitems()
andkeys()
.See also
INPUT:
binary
,integer
,real
– boolean. Set one of these arguments toTrue
to ensure that the variable gets the corresponding type.nonnegative
– boolean (default:False
); whether the variable should be assumed to be nonnegative. Rather useless for the binary typename
– string; associates a name to the variable. This is only useful when exporting the linear program to a file usingwrite_mps
orwrite_lp
, and has no other effect.indices
– (optional) an iterable of keys; components corresponding to these keys are created in order, and access to components with other keys will raise an error; otherwise components of this variable can be indexed by arbitrary keys and are created dynamically on access
OUTPUT:
A new instance of
MIPVariable
associated to the currentMixedIntegerLinearProgram
.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(); x MIPVariable with 0 real components sage: x0 = x[0]; x0 x_0
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(); x MIPVariable with 0 real components >>> x0 = x[Integer(0)]; x0 x_0
By default, variables are unbounded:
sage: print(p.get_min(x0)) None sage: print(p.get_max(x0)) None
>>> from sage.all import * >>> print(p.get_min(x0)) None >>> print(p.get_max(x0)) None
To define two dictionaries of variables, the first being of real type, and the second of integer type
sage: x = p.new_variable(real=True, nonnegative=True) sage: y = p.new_variable(integer=True, nonnegative=True) sage: p.add_constraint(x[2] + y[3,5], max=2) sage: p.is_integer(x[2]) False sage: p.is_integer(y[3,5]) True
>>> from sage.all import * >>> x = p.new_variable(real=True, nonnegative=True) >>> y = p.new_variable(integer=True, nonnegative=True) >>> p.add_constraint(x[Integer(2)] + y[Integer(3),Integer(5)], max=Integer(2)) >>> p.is_integer(x[Integer(2)]) False >>> p.is_integer(y[Integer(3),Integer(5)]) True
An exception is raised when two types are supplied
sage: z = p.new_variable(real=True, integer=True) Traceback (most recent call last): ... ValueError: Exactly one of the available types has to be True
>>> from sage.all import * >>> z = p.new_variable(real=True, integer=True) Traceback (most recent call last): ... ValueError: Exactly one of the available types has to be True
Unbounded variables:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(real=True) sage: y = p.new_variable(integer=True) sage: p.add_constraint(x[0] + x[3] <= 8) sage: p.add_constraint(y[0] >= y[1]) sage: p.show() Maximization: Constraints: x_0 + x_1 <= 8.0 - x_2 + x_3 <= 0.0 Variables: x_0 is a continuous variable (min=-oo, max=+oo) x_1 is a continuous variable (min=-oo, max=+oo) x_2 is an integer variable (min=-oo, max=+oo) x_3 is an integer variable (min=-oo, max=+oo)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(real=True) >>> y = p.new_variable(integer=True) >>> p.add_constraint(x[Integer(0)] + x[Integer(3)] <= Integer(8)) >>> p.add_constraint(y[Integer(0)] >= y[Integer(1)]) >>> p.show() Maximization: <BLANKLINE> Constraints: x_0 + x_1 <= 8.0 - x_2 + x_3 <= 0.0 Variables: x_0 is a continuous variable (min=-oo, max=+oo) x_1 is a continuous variable (min=-oo, max=+oo) x_2 is an integer variable (min=-oo, max=+oo) x_3 is an integer variable (min=-oo, max=+oo)
On the Sage command line, generator syntax is accepted as a shorthand for generating new variables with default settings:
sage: mip.<x, y, z> = MixedIntegerLinearProgram(solver='GLPK') sage: mip.add_constraint(x[0] + y[1] + z[2] <= 10) sage: mip.show() Maximization: Constraints: x[0] + y[1] + z[2] <= 10.0 Variables: x[0] = x_0 is a continuous variable (min=-oo, max=+oo) y[1] = x_1 is a continuous variable (min=-oo, max=+oo) z[2] = x_2 is a continuous variable (min=-oo, max=+oo)
>>> from sage.all import * >>> mip = MixedIntegerLinearProgram(solver='GLPK', names=('x', 'y', 'z',)); (x, y, z,) = mip._first_ngens(3) >>> mip.add_constraint(x[Integer(0)] + y[Integer(1)] + z[Integer(2)] <= Integer(10)) >>> mip.show() Maximization: <BLANKLINE> Constraints: x[0] + y[1] + z[2] <= 10.0 Variables: x[0] = x_0 is a continuous variable (min=-oo, max=+oo) y[1] = x_1 is a continuous variable (min=-oo, max=+oo) z[2] = x_2 is a continuous variable (min=-oo, max=+oo)
- number_of_constraints()[source]¶
Return the number of constraints assigned so far.
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.add_constraint(p[0] - p[2], min=1, max=4) sage: p.add_constraint(p[0] - 2*p[1], min=1) sage: p.number_of_constraints() 2
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.add_constraint(p[Integer(0)] - p[Integer(2)], min=Integer(1), max=Integer(4)) >>> p.add_constraint(p[Integer(0)] - Integer(2)*p[Integer(1)], min=Integer(1)) >>> p.number_of_constraints() 2
- number_of_variables()[source]¶
Return the number of variables used so far.
Note that this is backend-dependent, i.e. we count solver’s variables rather than user’s variables. An example of the latter can be seen below: Gurobi converts double inequalities, i.e. inequalities like \(m <= c^T x <= M\), with \(m<M\), into equations, by adding extra variables: \(c^T x + y = M\), \(0 <= y <= M-m\).
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.add_constraint(p[0] - p[2], max=4) sage: p.number_of_variables() 2 sage: p.add_constraint(p[0] - 2*p[1], min=1) sage: p.number_of_variables() 3 sage: p = MixedIntegerLinearProgram(solver='glpk') sage: p.add_constraint(p[0] - p[2], min=1, max=4) sage: p.number_of_variables() 2 sage: p = MixedIntegerLinearProgram(solver='gurobi') # optional - Gurobi sage: p.add_constraint(p[0] - p[2], min=1, max=4) # optional - Gurobi sage: p.number_of_variables() # optional - Gurobi 3
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.add_constraint(p[Integer(0)] - p[Integer(2)], max=Integer(4)) >>> p.number_of_variables() 2 >>> p.add_constraint(p[Integer(0)] - Integer(2)*p[Integer(1)], min=Integer(1)) >>> p.number_of_variables() 3 >>> p = MixedIntegerLinearProgram(solver='glpk') >>> p.add_constraint(p[Integer(0)] - p[Integer(2)], min=Integer(1), max=Integer(4)) >>> p.number_of_variables() 2 >>> p = MixedIntegerLinearProgram(solver='gurobi') # optional - Gurobi >>> p.add_constraint(p[Integer(0)] - p[Integer(2)], min=Integer(1), max=Integer(4)) # optional - Gurobi >>> p.number_of_variables() # optional - Gurobi 3
- polyhedron(**kwds)[source]¶
Return the polyhedron defined by the Linear Program.
INPUT:
All arguments given to this method are forwarded to the constructor of the
Polyhedron()
class.OUTPUT:
A
Polyhedron()
object whose \(i\)-th variable represents the \(i\)-th variable ofself
.Warning
The polyhedron is built from the variables stored by the LP solver (i.e. the output of
show()
). While they usually match the ones created explicitly when defining the LP, a solver like Gurobi has been known to introduce additional variables to store constraints of the typelower_bound <= linear_function <= upper bound
. You should be fine if you did not install Gurobi or if you do not use it as a solver, but keep an eye on the number of variables in the polyhedron, or on the output ofshow()
. Just in case.See also
to_linear_program()
– return theMixedIntegerLinearProgram
object associated with aPolyhedron()
object.EXAMPLES:
A LP on two variables:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.add_constraint(0 <= 2*p['x'] + p['y'] <= 1) sage: p.add_constraint(0 <= 3*p['y'] + p['x'] <= 2) sage: P = p.polyhedron(); P A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 4 vertices
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.add_constraint(Integer(0) <= Integer(2)*p['x'] + p['y'] <= Integer(1)) >>> p.add_constraint(Integer(0) <= Integer(3)*p['y'] + p['x'] <= Integer(2)) >>> P = p.polyhedron(); P A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 4 vertices
3-D Polyhedron:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.add_constraint(0 <= 2*p['x'] + p['y'] + 3*p['z'] <= 1) sage: p.add_constraint(0 <= 2*p['y'] + p['z'] + 3*p['x'] <= 1) sage: p.add_constraint(0 <= 2*p['z'] + p['x'] + 3*p['y'] <= 1) sage: P = p.polyhedron(); P A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 8 vertices
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.add_constraint(Integer(0) <= Integer(2)*p['x'] + p['y'] + Integer(3)*p['z'] <= Integer(1)) >>> p.add_constraint(Integer(0) <= Integer(2)*p['y'] + p['z'] + Integer(3)*p['x'] <= Integer(1)) >>> p.add_constraint(Integer(0) <= Integer(2)*p['z'] + p['x'] + Integer(3)*p['y'] <= Integer(1)) >>> P = p.polyhedron(); P A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 8 vertices
An empty polyhedron:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.add_constraint(2*v['x'] + v['y'] + 3*v['z'] <= 1) sage: p.add_constraint(2*v['y'] + v['z'] + 3*v['x'] <= 1) sage: p.add_constraint(2*v['z'] + v['x'] + 3*v['y'] >= 2) sage: P = p.polyhedron(); P The empty polyhedron in RDF^3
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.add_constraint(Integer(2)*v['x'] + v['y'] + Integer(3)*v['z'] <= Integer(1)) >>> p.add_constraint(Integer(2)*v['y'] + v['z'] + Integer(3)*v['x'] <= Integer(1)) >>> p.add_constraint(Integer(2)*v['z'] + v['x'] + Integer(3)*v['y'] >= Integer(2)) >>> P = p.polyhedron(); P The empty polyhedron in RDF^3
An unbounded polyhedron:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.add_constraint(2*p['x'] + p['y'] - p['z'] <= 1) sage: P = p.polyhedron(); P A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 1 ray, 2 lines
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.add_constraint(Integer(2)*p['x'] + p['y'] - p['z'] <= Integer(1)) >>> P = p.polyhedron(); P A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 1 vertex, 1 ray, 2 lines
A square (see Issue #14395)
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x,y = p['x'], p['y'] sage: p.add_constraint(x <= 1) sage: p.add_constraint(x >= -1) sage: p.add_constraint(y <= 1) sage: p.add_constraint(y >= -1) sage: p.polyhedron() A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 4 vertices
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x,y = p['x'], p['y'] >>> p.add_constraint(x <= Integer(1)) >>> p.add_constraint(x >= -Integer(1)) >>> p.add_constraint(y <= Integer(1)) >>> p.add_constraint(y >= -Integer(1)) >>> p.polyhedron() A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 4 vertices
We can also use a backend that supports exact arithmetic:
sage: p = MixedIntegerLinearProgram(solver='PPL') sage: x,y = p['x'], p['y'] sage: p.add_constraint(x <= 1) sage: p.add_constraint(x >= -1) sage: p.add_constraint(y <= 1) sage: p.add_constraint(y >= -1) sage: p.polyhedron() A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='PPL') >>> x,y = p['x'], p['y'] >>> p.add_constraint(x <= Integer(1)) >>> p.add_constraint(x >= -Integer(1)) >>> p.add_constraint(y <= Integer(1)) >>> p.add_constraint(y >= -Integer(1)) >>> p.polyhedron() A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
- remove_constraint(i)[source]¶
Removes a constraint from
self
.INPUT:
i
– index of the constraint to remove
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x, y = p[0], p[1] sage: p.add_constraint(x + y, max=10) sage: p.add_constraint(x - y, max=0) sage: p.add_constraint(x, max=4) sage: p.show() Maximization: Constraints: x_0 + x_1 <= 10.0 x_0 - x_1 <= 0.0 x_0 <= 4.0 ... sage: p.remove_constraint(1) sage: p.show() Maximization: Constraints: x_0 + x_1 <= 10.0 x_0 <= 4.0 ... sage: p.number_of_constraints() 2
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x, y = p[Integer(0)], p[Integer(1)] >>> p.add_constraint(x + y, max=Integer(10)) >>> p.add_constraint(x - y, max=Integer(0)) >>> p.add_constraint(x, max=Integer(4)) >>> p.show() Maximization: <BLANKLINE> Constraints: x_0 + x_1 <= 10.0 x_0 - x_1 <= 0.0 x_0 <= 4.0 ... >>> p.remove_constraint(Integer(1)) >>> p.show() Maximization: <BLANKLINE> Constraints: x_0 + x_1 <= 10.0 x_0 <= 4.0 ... >>> p.number_of_constraints() 2
- remove_constraints(constraints)[source]¶
Remove several constraints.
INPUT:
constraints
– an iterable containing the indices of the rows to remove
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x, y = p[0], p[1] sage: p.add_constraint(x + y, max=10) sage: p.add_constraint(x - y, max=0) sage: p.add_constraint(x, max=4) sage: p.show() Maximization: Constraints: x_0 + x_1 <= 10.0 x_0 - x_1 <= 0.0 x_0 <= 4.0 ... sage: p.remove_constraints([0, 1]) sage: p.show() Maximization: Constraints: x_0 <= 4.0 ... sage: p.number_of_constraints() 1
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x, y = p[Integer(0)], p[Integer(1)] >>> p.add_constraint(x + y, max=Integer(10)) >>> p.add_constraint(x - y, max=Integer(0)) >>> p.add_constraint(x, max=Integer(4)) >>> p.show() Maximization: <BLANKLINE> Constraints: x_0 + x_1 <= 10.0 x_0 - x_1 <= 0.0 x_0 <= 4.0 ... >>> p.remove_constraints([Integer(0), Integer(1)]) >>> p.show() Maximization: <BLANKLINE> Constraints: x_0 <= 4.0 ... >>> p.number_of_constraints() 1
When checking for redundant constraints, make sure you remove only the constraints that were actually added. Problems could arise if you have a function that builds lps non-interactively, but it fails to check whether adding a constraint actually increases the number of constraints. The function might later try to remove constraints that are not actually there:
sage: p = MixedIntegerLinearProgram(check_redundant=True, solver='GLPK') sage: x, y = p[0], p[1] sage: p.add_constraint(x + y, max=10) sage: for each in range(10): ....: p.add_constraint(x - y, max=10) sage: p.add_constraint(x, max=4) sage: p.number_of_constraints() 3 sage: p.remove_constraints(range(1, 9)) Traceback (most recent call last): ... IndexError: pop index out of range sage: p.remove_constraint(1) sage: p.number_of_constraints() 2
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(check_redundant=True, solver='GLPK') >>> x, y = p[Integer(0)], p[Integer(1)] >>> p.add_constraint(x + y, max=Integer(10)) >>> for each in range(Integer(10)): ... p.add_constraint(x - y, max=Integer(10)) >>> p.add_constraint(x, max=Integer(4)) >>> p.number_of_constraints() 3 >>> p.remove_constraints(range(Integer(1), Integer(9))) Traceback (most recent call last): ... IndexError: pop index out of range >>> p.remove_constraint(Integer(1)) >>> p.number_of_constraints() 2
We should now be able to add the old constraint back in:
sage: for each in range(10): ....: p.add_constraint(x - y, max=10) sage: p.number_of_constraints() 3
>>> from sage.all import * >>> for each in range(Integer(10)): ... p.add_constraint(x - y, max=Integer(10)) >>> p.number_of_constraints() 3
- set_binary(ee)[source]¶
Set a variable or a
MIPVariable
as binary.INPUT:
ee
– an instance ofMIPVariable
or one of its elements
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(nonnegative=True)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(nonnegative=True)
With the following instruction, all the variables from x will be binary:
sage: p.set_binary(x) sage: p.set_objective(x[0] + x[1]) sage: p.add_constraint(-3*x[0] + 2*x[1], max=2)
>>> from sage.all import * >>> p.set_binary(x) >>> p.set_objective(x[Integer(0)] + x[Integer(1)]) >>> p.add_constraint(-Integer(3)*x[Integer(0)] + Integer(2)*x[Integer(1)], max=Integer(2))
It is still possible, though, to set one of these variables as integer while keeping the others as they are:
sage: p.set_integer(x[3])
>>> from sage.all import * >>> p.set_integer(x[Integer(3)])
- set_integer(ee)[source]¶
Set a variable or a
MIPVariable
as integer.INPUT:
ee
– an instance ofMIPVariable
or one of its elements
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(nonnegative=True)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(nonnegative=True)
With the following instruction, all the variables from x will be integers:
sage: p.set_integer(x) sage: p.set_objective(x[0] + x[1]) sage: p.add_constraint(-3*x[0] + 2*x[1], max=2)
>>> from sage.all import * >>> p.set_integer(x) >>> p.set_objective(x[Integer(0)] + x[Integer(1)]) >>> p.add_constraint(-Integer(3)*x[Integer(0)] + Integer(2)*x[Integer(1)], max=Integer(2))
It is still possible, though, to set one of these variables as binary while keeping the others as they are:
sage: p.set_binary(x[3])
>>> from sage.all import * >>> p.set_binary(x[Integer(3)])
- set_max(v, max)[source]¶
Set the maximum value of a variable.
INPUT:
v
– a variablemax
– the maximum value the variable can take; whenmax=None
, the variable has no upper bound
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.set_objective(v[1]) sage: p.get_max(v[1]) sage: p.set_max(v[1],6) sage: p.get_max(v[1]) 6.0
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.set_objective(v[Integer(1)]) >>> p.get_max(v[Integer(1)]) >>> p.set_max(v[Integer(1)],Integer(6)) >>> p.get_max(v[Integer(1)]) 6.0
With a
MIPVariable
as an argument:sage: vv = p.new_variable(real=True) sage: p.get_max(vv) sage: p.get_max(vv[0]) sage: p.set_max(vv,5) sage: p.get_max(vv[0]) 5.0 sage: p.get_max(vv[9]) 5.0
>>> from sage.all import * >>> vv = p.new_variable(real=True) >>> p.get_max(vv) >>> p.get_max(vv[Integer(0)]) >>> p.set_max(vv,Integer(5)) >>> p.get_max(vv[Integer(0)]) 5.0 >>> p.get_max(vv[Integer(9)]) 5.0
- set_min(v, min)[source]¶
Set the minimum value of a variable.
INPUT:
v
– a variablemin
– the minimum value the variable can take; whenmin=None
, the variable has no lower bound
See also
get_min()
– get the minimum value of a variable
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True) sage: p.set_objective(v[1]) sage: p.get_min(v[1]) 0.0 sage: p.set_min(v[1],6) sage: p.get_min(v[1]) 6.0 sage: p.set_min(v[1], None) sage: p.get_min(v[1])
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True) >>> p.set_objective(v[Integer(1)]) >>> p.get_min(v[Integer(1)]) 0.0 >>> p.set_min(v[Integer(1)],Integer(6)) >>> p.get_min(v[Integer(1)]) 6.0 >>> p.set_min(v[Integer(1)], None) >>> p.get_min(v[Integer(1)])
With a
MIPVariable
as an argument:sage: vv = p.new_variable(real=True) sage: p.get_min(vv) sage: p.get_min(vv[0]) sage: p.set_min(vv,5) sage: p.get_min(vv[0]) 5.0 sage: p.get_min(vv[9]) 5.0
>>> from sage.all import * >>> vv = p.new_variable(real=True) >>> p.get_min(vv) >>> p.get_min(vv[Integer(0)]) >>> p.set_min(vv,Integer(5)) >>> p.get_min(vv[Integer(0)]) 5.0 >>> p.get_min(vv[Integer(9)]) 5.0
- set_objective(obj)[source]¶
Set the objective of the
MixedIntegerLinearProgram
.INPUT:
obj
– a linear function to be optimized ( can also be set toNone
or0
or any number when just looking for a feasible solution )
EXAMPLES:
Let’s solve the following linear program:
Maximize: x + 5 * y Constraints: x + 0.2 y <= 4 1.5 * x + 3 * y <= 4 Variables: x is Real (min = 0, max = None) y is Real (min = 0, max = None)
This linear program can be solved as follows:
sage: p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[1] + 5*x[2]) sage: p.add_constraint(x[1] + 2/10*x[2], max=4) sage: p.add_constraint(1.5*x[1] + 3*x[2], max=4) sage: round(p.solve(),5) 6.66667 sage: p.set_objective(None) sage: _ = p.solve()
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(1)] + Integer(5)*x[Integer(2)]) >>> p.add_constraint(x[Integer(1)] + Integer(2)/Integer(10)*x[Integer(2)], max=Integer(4)) >>> p.add_constraint(RealNumber('1.5')*x[Integer(1)] + Integer(3)*x[Integer(2)], max=Integer(4)) >>> round(p.solve(),Integer(5)) 6.66667 >>> p.set_objective(None) >>> _ = p.solve()
- set_problem_name(name)[source]¶
Set the name of the
MixedIntegerLinearProgram
.INPUT:
name
– string representing the name of theMixedIntegerLinearProgram
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.set_problem_name("Test program") sage: p Mixed Integer Program "Test program" (no objective, 0 variables, 0 constraints)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.set_problem_name("Test program") >>> p Mixed Integer Program "Test program" (no objective, 0 variables, 0 constraints)
- set_real(ee)[source]¶
Set a variable or a
MIPVariable
as real.INPUT:
ee
– an instance ofMIPVariable
or one of its elements
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(nonnegative=True)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(nonnegative=True)
With the following instruction, all the variables from x will be real:
sage: p.set_real(x) sage: p.set_objective(x[0] + x[1]) sage: p.add_constraint(-3*x[0] + 2*x[1], max=2) It is still possible, though, to set one of these variables as binary while keeping the others as they are:: sage: p.set_binary(x[3])
- show()[source]¶
Displays the
MixedIntegerLinearProgram
in a human-readable way.EXAMPLES:
When constraints and variables have names
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(name='Hey') sage: p.set_objective(x[1] + x[2]) sage: p.add_constraint(-3*x[1] + 2*x[2], max=2, name='Constraint_1') sage: p.show() Maximization: Hey[1] + Hey[2] Constraints: Constraint_1: -3.0 Hey[1] + 2.0 Hey[2] <= 2.0 Variables: Hey[1] = x_0 is a continuous variable (min=-oo, max=+oo) Hey[2] = x_1 is a continuous variable (min=-oo, max=+oo)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(name='Hey') >>> p.set_objective(x[Integer(1)] + x[Integer(2)]) >>> p.add_constraint(-Integer(3)*x[Integer(1)] + Integer(2)*x[Integer(2)], max=Integer(2), name='Constraint_1') >>> p.show() Maximization: Hey[1] + Hey[2] Constraints: Constraint_1: -3.0 Hey[1] + 2.0 Hey[2] <= 2.0 Variables: Hey[1] = x_0 is a continuous variable (min=-oo, max=+oo) Hey[2] = x_1 is a continuous variable (min=-oo, max=+oo)
Without any names
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[1] + x[2]) sage: p.add_constraint(-3*x[1] + 2*x[2], max=2) sage: p.show() Maximization: x_0 + x_1 Constraints: -3.0 x_0 + 2.0 x_1 <= 2.0 Variables: x_0 is a continuous variable (min=0.0, max=+oo) x_1 is a continuous variable (min=0.0, max=+oo)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(1)] + x[Integer(2)]) >>> p.add_constraint(-Integer(3)*x[Integer(1)] + Integer(2)*x[Integer(2)], max=Integer(2)) >>> p.show() Maximization: x_0 + x_1 Constraints: -3.0 x_0 + 2.0 x_1 <= 2.0 Variables: x_0 is a continuous variable (min=0.0, max=+oo) x_1 is a continuous variable (min=0.0, max=+oo)
With \(\QQ\) coefficients:
sage: p = MixedIntegerLinearProgram(solver='ppl') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[1] + 1/2*x[2]) sage: p.add_constraint(-3/5*x[1] + 2/7*x[2], max=2/5) sage: p.show() Maximization: x_0 + 1/2 x_1 Constraints: constraint_0: -3/5 x_0 + 2/7 x_1 <= 2/5 Variables: x_0 is a continuous variable (min=0, max=+oo) x_1 is a continuous variable (min=0, max=+oo)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='ppl') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(1)] + Integer(1)/Integer(2)*x[Integer(2)]) >>> p.add_constraint(-Integer(3)/Integer(5)*x[Integer(1)] + Integer(2)/Integer(7)*x[Integer(2)], max=Integer(2)/Integer(5)) >>> p.show() Maximization: x_0 + 1/2 x_1 Constraints: constraint_0: -3/5 x_0 + 2/7 x_1 <= 2/5 Variables: x_0 is a continuous variable (min=0, max=+oo) x_1 is a continuous variable (min=0, max=+oo)
With a constant term in the objective:
sage: p = MixedIntegerLinearProgram(solver='ppl') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[0] + 42) sage: p.show() Maximization: x_0 + 42 Constraints: Variables: x_0 is a continuous variable (min=0, max=+oo)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='ppl') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(0)] + Integer(42)) >>> p.show() Maximization: x_0 + 42 Constraints: Variables: x_0 is a continuous variable (min=0, max=+oo)
- solve(log=None, objective_only=False)[source]¶
Solve the
MixedIntegerLinearProgram
.INPUT:
log
– integer (default:None
); the verbosity level. Indicates whether progress should be printed during computation. The solver is initialized to report no progress.objective_only
– boolean:When set to
True
, only the objective function is returned.When set to
False
(default), the optimal numerical values are stored (takes computational time).
OUTPUT: the optimal value taken by the objective function
Warning
By default, no additional assumption is made on the domain of an LP variable. See
set_min()
andset_max()
to change it.EXAMPLES:
Consider the following linear program:
Maximize: x + 5 * y Constraints: x + 0.2 y <= 4 1.5 * x + 3 * y <= 4 Variables: x is Real (min = 0, max = None) y is Real (min = 0, max = None)
This linear program can be solved as follows:
sage: p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[1] + 5*x[2]) sage: p.add_constraint(x[1] + 0.2*x[2], max=4) sage: p.add_constraint(1.5*x[1] + 3*x[2], max=4) sage: round(p.solve(),6) 6.666667 sage: x = p.get_values(x) sage: round(x[1],6) # abs tol 1e-15 0.0 sage: round(x[2],6) 1.333333 Computation of a maximum stable set in Petersen's graph:: sage: # needs sage.graphs sage: g = graphs.PetersenGraph() sage: p = MixedIntegerLinearProgram(maximization=True, solver='GLPK') sage: b = p.new_variable(nonnegative=True) sage: p.set_objective(sum([b[v] for v in g])) sage: for (u,v) in g.edges(sort=False, labels=None): ....: p.add_constraint(b[u] + b[v], max=1) sage: p.set_binary(b) sage: p.solve(objective_only=True) 4.0
Constraints in the objective function are respected:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x, y = p[0], p[1] sage: p.add_constraint(2*x + 3*y, max=6) sage: p.add_constraint(3*x + 2*y, max=6) sage: p.set_objective(x + y + 7) sage: p.set_integer(x); p.set_integer(y) sage: p.solve() 9.0
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x, y = p[Integer(0)], p[Integer(1)] >>> p.add_constraint(Integer(2)*x + Integer(3)*y, max=Integer(6)) >>> p.add_constraint(Integer(3)*x + Integer(2)*y, max=Integer(6)) >>> p.set_objective(x + y + Integer(7)) >>> p.set_integer(x); p.set_integer(y) >>> p.solve() 9.0
- solver_parameter(name, value=None)[source]¶
Return or define a solver parameter.
The solver parameters are by essence solver-specific, which means their meaning heavily depends on the solver used.
(If you do not know which solver you are using, then you use GLPK).
Aliases:
Very common parameters have aliases making them solver-independent. For example, the following:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.solver_parameter("timelimit", 60)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.solver_parameter("timelimit", Integer(60))
Sets the solver to stop its computations after 60 seconds, and works with GLPK, CPLEX , SCIP, and Gurobi.
'timelimit'
– defines the maximum time spent on a computation (measured in seconds)
Another example is the
'logfile'
parameter, which is used to specify the file in which computation logs are recorded. By default, the logs are not recorded, and we can disable this feature providing an empty filename. This is currently working with CPLEX and Gurobi:sage: # optional - cplex sage: p = MixedIntegerLinearProgram(solver='CPLEX') sage: p.solver_parameter("logfile") '' sage: p.solver_parameter("logfile", "/dev/null") sage: p.solver_parameter("logfile") '/dev/null' sage: p.solver_parameter("logfile", '') sage: p.solver_parameter("logfile") ''
>>> from sage.all import * >>> # optional - cplex >>> p = MixedIntegerLinearProgram(solver='CPLEX') >>> p.solver_parameter("logfile") '' >>> p.solver_parameter("logfile", "/dev/null") >>> p.solver_parameter("logfile") '/dev/null' >>> p.solver_parameter("logfile", '') >>> p.solver_parameter("logfile") ''
Solver-specific parameters:
GLPK : We have implemented very close to comprehensive coverage of the GLPK solver parameters for the simplex and integer optimization methods. For details, see the documentation of
GLPKBackend.solver_parameter
.CPLEX’s parameters are identified by a string. Their list is available on ILOG’s website.
The command
sage: p = MixedIntegerLinearProgram(solver='CPLEX') # optional - CPLEX sage: p.solver_parameter("CPX_PARAM_TILIM", 60) # optional - CPLEX
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='CPLEX') # optional - CPLEX >>> p.solver_parameter("CPX_PARAM_TILIM", Integer(60)) # optional - CPLEX
works as intended.
Gurobi’s parameters should all be available through this method. Their list is available on Gurobi’s website http://www.gurobi.com/documentation/5.5/reference-manual/node798.
SCIP’s parameter can be found here: http://scip.zib.de/doc-5.0.1/html/PARAMETERS.php.
INPUT:
name
– string; the parametervalue
– the parameter’s value if it is to be defined, orNone
(default) to obtain its current value
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: p.solver_parameter("timelimit", 60) sage: p.solver_parameter("timelimit") 60.0
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> p.solver_parameter("timelimit", Integer(60)) >>> p.solver_parameter("timelimit") 60.0
- sum(L)[source]¶
Efficiently compute the sum of a sequence of
LinearFunction
elementsINPUT:
mip
– theMixedIntegerLinearProgram
parentL
– list ofLinearFunction
instances
Note
The use of the regular
sum
function is not recommended as it is much less efficient than this oneEXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: v = p.new_variable(nonnegative=True)
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> v = p.new_variable(nonnegative=True)
The following command:
sage: s = p.sum(v[i] for i in range(90))
>>> from sage.all import * >>> s = p.sum(v[i] for i in range(Integer(90)))
is much more efficient than:
sage: s = sum(v[i] for i in range(90))
>>> from sage.all import * >>> s = sum(v[i] for i in range(Integer(90)))
- write_lp(filename)[source]¶
Write the linear program as a LP file.
This function export the problem as a LP file.
INPUT:
filename
– the file in which you want the problem to be written
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[1] + x[2]) sage: p.add_constraint(-3*x[1] + 2*x[2], max=2) sage: import tempfile sage: with tempfile.NamedTemporaryFile(suffix='.lp') as f: ....: p.write_lp(f.name) Writing problem data to ... 9 lines were written
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(1)] + x[Integer(2)]) >>> p.add_constraint(-Integer(3)*x[Integer(1)] + Integer(2)*x[Integer(2)], max=Integer(2)) >>> import tempfile >>> with tempfile.NamedTemporaryFile(suffix='.lp') as f: ... p.write_lp(f.name) Writing problem data to ... 9 lines were written
For more information about the LP file format : http://lpsolve.sourceforge.net/5.5/lp-format.htm
- write_mps(filename, modern=True)[source]¶
Write the linear program as a MPS file.
This function export the problem as a MPS file.
INPUT:
filename
– the file in which you want the problem to be writtenmodern
– lets you choose between Fixed MPS and Free MPS:True
– outputs the problem in Free MPSFalse
– outputs the problem in Fixed MPS
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x = p.new_variable(nonnegative=True) sage: p.set_objective(x[1] + x[2]) sage: p.add_constraint(-3*x[1] + 2*x[2], max=2, name='OneConstraint') sage: import tempfile sage: with tempfile.NamedTemporaryFile(suffix='.mps') as f: ....: p.write_mps(f.name) Writing problem data to ... 17 records were written
>>> from sage.all import * >>> p = MixedIntegerLinearProgram(solver='GLPK') >>> x = p.new_variable(nonnegative=True) >>> p.set_objective(x[Integer(1)] + x[Integer(2)]) >>> p.add_constraint(-Integer(3)*x[Integer(1)] + Integer(2)*x[Integer(2)], max=Integer(2), name='OneConstraint') >>> import tempfile >>> with tempfile.NamedTemporaryFile(suffix='.mps') as f: ... p.write_mps(f.name) Writing problem data to ... 17 records were written
For information about the MPS file format, see Wikipedia article MPS_(format)