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

\[\max \{ c^T x \;|\; A x \leq b, x \geq 0 \}\]

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 variables w via w = 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 as None.

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

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(maximization=False, solver='GLPK')
w = p.new_variable(integer=True, nonnegative=True)
p.add_constraint(w[0] + w[1] + w[2] - 14*w[3] == 0)
p.add_constraint(w[1] + 2*w[2] - 8*w[3] == 0)
p.add_constraint(2*w[2] - 3*w[3] == 0)
p.add_constraint(w[0] - w[1] - w[2] >= 0)
p.add_constraint(w[3] >= 1)
p.set_objective(w[3])
p.show()
print('Objective Value: {}'.format(p.solve()))
for i, v in sorted(p.get_values(w, convert=ZZ, tolerance=1e-3).items()):
    print(f'w_{i} = {v}')

Different backends compute with different base fields, for example:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.base_ring()
x = p.new_variable(real=True, nonnegative=True)
0.5 + 3/2*x[1]
p = MixedIntegerLinearProgram(solver='ppl')
p.base_ring()
x = p.new_variable(nonnegative=True)
0.5 + 3/2*x[1]

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

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

Python

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

Sage Live

mip.<a,b> = MixedIntegerLinearProgram(solver='GLPK')
a
5 + a[1] + 2*b[3]

Indices can be any object, not necessarily integers. Multi-indices are also allowed:

Sage

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)

Python

>>> 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)

Sage Live

a[4, 'string', QQ]
a[4, 'string', QQ] - 7*b[2]
mip.show()

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

sage: mip = MixedIntegerLinearProgram(solver='GLPK')
sage: 5 + mip[2] + 2*mip[7]
5 + x_0 + 2*x_1

Python

>>> from sage.all import *
>>> mip = MixedIntegerLinearProgram(solver='GLPK')
>>> Integer(5) + mip[Integer(2)] + Integer(2)*mip[Integer(7)]
5 + x_0 + 2*x_1

Sage Live

mip = MixedIntegerLinearProgram(solver='GLPK')
5 + mip[2] + 2*mip[7]

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_constraint()`	Add a constraint to the `MixedIntegerLinearProgram`
`base_ring()`	Return the base ring
`best_known_objective_bound()`	Return the value of the currently best known bound
`constraints()`	Return a list of constraints, as 3-tuples
`default_variable()`	Return the default `MIPVariable` of `self`.
`get_backend()`	Return the backend instance used
`get_max()`	Return the maximum value of a variable
`get_min()`	Return the minimum value of a variable
`get_objective_value()`	Return the value of the objective function
`get_relative_objective_gap()`	Return the relative objective gap of the best known solution
`get_values()`	Return values found by the previous call to `solve()`
`is_binary()`	Test whether the variable `e` is binary
`is_integer()`	Test whether the variable is an integer
`is_real()`	Test whether the variable is real
`linear_constraints_parent()`	Return the parent for all linear constraints
`linear_functions_parent()`	Return the parent for all linear functions
`new_variable()`	Return an instance of `MIPVariable` associated
`number_of_constraints()`	Return the number of constraints assigned so far
`number_of_variables()`	Return the number of variables used so far
`polyhedron()`	Return the polyhedron defined by the Linear Program
`remove_constraint()`	Remove a constraint from self
`remove_constraints()`	Remove several constraints
`set_binary()`	Set a variable or a `MIPVariable` as binary
`set_integer()`	Set a variable or a `MIPVariable` as integer
`set_max()`	Set the maximum value of a variable
`set_min()`	Set the minimum value of a variable
`set_objective()`	Set the objective of the `MixedIntegerLinearProgram`
`set_problem_name()`	Set the name of the `MixedIntegerLinearProgram`
`set_real()`	Set a variable or a `MIPVariable` as real
`show()`	Display the `MixedIntegerLinearProgram` in a human-readable
`solve()`	Solve the `MixedIntegerLinearProgram`
`solver_parameter()`	Return or define a solver parameter
`sum()`	Efficiently computes the sum of a sequence of LinearFunction elements
`write_lp()`	Write the linear program as a LP file
`write_mps()`	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

sage: from sage.numerical.mip import MIPSolverException
sage: e = MIPSolverException("Error")
sage: e
MIPSolverException('Error'...)
sage: print(e)
Error

Python

>>> from sage.all import *
>>> from sage.numerical.mip import MIPSolverException
>>> e = MIPSolverException("Error")
>>> e
MIPSolverException('Error'...)
>>> print(e)
Error

Sage Live

from sage.numerical.mip import MIPSolverException
e = MIPSolverException("Error")
e
print(e)

class sage.numerical.mip.MIPVariable[source]¶

Bases: FiniteFamily

MIPVariable is a variable used by the class MixedIntegerLinearProgram.

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 new MixedIntegerLinearProgram instance mip.

For this to make sense, mip should have been obtained as a copy of self.mip().

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
pv = p.new_variable(nonnegative=True)
pv[0]
q = copy(p)
qv = pv.copy_for_mip(q)
pv[77]
p.number_of_variables()
q.number_of_variables()
qv[33]
p.number_of_variables()
q.number_of_variables()
p = MixedIntegerLinearProgram(solver='GLPK')
pv = p.new_variable(indices=[3, 7])
q = copy(p)
qv = pv.copy_for_mip(q)
qv[3]
qv[5]

items()[source]¶

Return the pairs (keys, value) contained in the dictionary.

EXAMPLES:

Sage

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)]

Python

>>> 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)]

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[0] + v[1])
sorted(v.items())

keys()[source]¶

Return the keys already defined in the dictionary.

EXAMPLES:

Sage

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]

Python

>>> 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]

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[0] + v[1])
sorted(v.keys())

mip()[source]¶

Return the MixedIntegerLinearProgram in which self is a variable.

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: v = p.new_variable(nonnegative=True)
sage: p == v.mip()
True

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> v = p.new_variable(nonnegative=True)
>>> p == v.mip()
True

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p == v.mip()

set_max(max)[source]¶

Set an upper bound on the variable.

INPUT:

max – an upper bound, or None to mean that the variable is unbounded

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(real=True, nonnegative=True)
p.get_max(v)
p.get_max(v[0])
p.set_max(v,4)
p.get_max(v)
p.get_max(v[0])

set_min(min)[source]¶

Set a lower bound on the variable.

INPUT:

min – a lower bound, or None to mean that the variable is unbounded

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(real=True, nonnegative=True)
p.get_min(v)
p.get_min(v[0])
p.set_min(v,4)
p.get_min(v)
p.get_min(v[0])

values()[source]¶

Return the symbolic variables associated to the current dictionary.

EXAMPLES:

Sage

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]

Python

>>> 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]

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[0] + v[1])
sorted(v.values(), key=str)

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 is QQ.
- If solver=None (default), the default solver is used (see default_mip_solver()).
- solver can also be a callable (such as a class), see sage.numerical.backends.generic_backend.get_solver() for examples.
maximization
- When set to True (default), the MixedIntegerLinearProgram is defined as a maximization.
- When set to False, the MixedIntegerLinearProgram is defined as a minimization.
constraint_generation – only used when solver=None
- When set to True, after solving the MixedIntegerLinearProgram, 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

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

Python

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

Sage Live

# 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=1)
p.solve(objective_only=True)

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 or max has to be specified.
- A linear constraint of the form A <= B, A >= B, A <= B <= C, A >= B >= C or A == B.
- A vector-valued linear function, see linear_tensor. In this case, one of the arguments min or max 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 or None (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 the linear_function argument is a symbolic (in)-equality.
min – constant or None (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 the linear_function argument is a symbolic (in)-equality.
name – a name for the constraint
return_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/or set_max of MixedIntegerLinearProgram.

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

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(maximization=True, solver='GLPK')
x = p.new_variable(nonnegative=True)
p.set_objective(x[0] + 5*x[1])
p.add_constraint(x[0] + 0.2*x[1], max=4)
p.add_constraint(1.5*x[0] + 3*x[1], max=4)
p.solve()     # rel tol 1e-15

There are two different ways to add the constraint x[5] + 3*x[7] <= x[6] + 3 to a MixedIntegerLinearProgram.

The first one consists in giving add_constraint this very expression:

Sage

sage: p.add_constraint(x[5] + 3*x[7] <= x[6] + 3)

Python

>>> from sage.all import *
>>> p.add_constraint(x[Integer(5)] + Integer(3)*x[Integer(7)] <= x[Integer(6)] + Integer(3))

Sage Live

p.add_constraint(x[5] + 3*x[7] <= x[6] + 3)

The second (slightly more efficient) one is to use the arguments min or max, which can only be numerical values:

Sage

sage: p.add_constraint(x[5] + 3*x[7] - x[6], max=3)

Python

>>> from sage.all import *
>>> p.add_constraint(x[Integer(5)] + Integer(3)*x[Integer(7)] - x[Integer(6)], max=Integer(3))

Sage Live

p.add_constraint(x[5] + 3*x[7] - x[6], max=3)

One can also define double-bounds or equality using symbols <=, >= and ==:

Sage

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)

Python

>>> 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))

Sage Live

p.add_constraint(x[5] + 3*x[7] == x[6] + 3)
p.add_constraint(x[5] + 3*x[7] <= x[6] + 3 <= x[8] + 27)

Using this notation, the previous program can be written as:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(maximization=True, solver='GLPK')
x = p.new_variable(nonnegative=True)
p.set_objective(x[0] + 5*x[1])
p.add_constraint(x[0] + 0.2*x[1] <= 4)
p.add_constraint(1.5*x[0] + 3*x[1] <= 4)
p.solve()     # rel tol 1e-15

The two constraints can also be combined into a single vector-valued constraint:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(maximization=True, solver='GLPK')
x = p.new_variable(nonnegative=True)
p.set_objective(x[0] + 5*x[1])
f_vec = vector([1, 1.5]) * x[0] + vector([0.2, 3]) * x[1];  f_vec
p.add_constraint(f_vec, max=vector([4, 4]))
p.solve()     # rel tol 1e-15

Instead of specifying the maximum in the optional max argument, we can also use (in)equality notation for vector-valued linear functions:

Sage

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

Python

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

Sage Live

f_vec <= 4    # constant rhs becomes vector
p = MixedIntegerLinearProgram(maximization=True, solver='GLPK')
x = p.new_variable(nonnegative=True)
p.set_objective(x[0] + 5*x[1])
p.add_constraint(f_vec <= 4)
p.solve()     # rel tol 1e-15

Finally, one can use the matrix * MIPVariable notation to write vector-valued linear functions:

Sage

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

Python

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

Sage Live

m = matrix([[1.0, 0.2], [1.5, 3.0]]);  m
p = MixedIntegerLinearProgram(maximization=True, solver='GLPK')
x = p.new_variable(nonnegative=True)
p.set_objective(x[0] + 5*x[1])
p.add_constraint(m * x <= 4)
p.solve()     # rel tol 1e-15

base_ring()[source]¶

Return the base ring.

OUTPUT: a ring. The coefficients that the chosen solver supports

EXAMPLES:

Sage

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?

Python

>>> 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?

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.base_ring()
p = MixedIntegerLinearProgram(solver='ppl')
p.base_ring()
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
# needs sage.groups sage.rings.number_field
d = polytopes.dodecahedron()
p = MixedIntegerLinearProgram(base_ring=d.base_ring())
p.base_ring()

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 (cf solver_parameter()).

Note

Has no meaning unless solve has been called before.

EXAMPLES:

Sage

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

Python

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

Sage Live

# needs sage.graphs
g = graphs.CubeGraph(9)
p = MixedIntegerLinearProgram(solver='GLPK')
p.solver_parameter("mip_gap_tolerance",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)) <= 1)
p.add_constraint(b[v] == 1)  # Force an easy non-0 solution
p.solve() # rel tol 100
p.best_known_objective_bound()  # random

constraints(indices=None)[source]¶

Return a list of constraints, as 3-tuples.

INPUT:

indices – select which constraint(s) to return
- If 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 variable indices[i] the coefficient coefficients[i], and \(0\) to all the others.

lower_bound and upper_bound are numerical values.

EXAMPLES:

First, let us define a small LP:

Sage

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)

Python

>>> 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))

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.add_constraint(p[0] - p[2], min=1, max=4)
p.add_constraint(p[0] - 2*p[1], min=1)

To obtain the list of all constraints:

Sage

sage: p.constraints()          # not tested
[(1.0, ([1, 0], [-1.0, 1.0]), 4.0), (1.0, ([2, 0], [-2.0, 1.0]), None)]

Python

>>> 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)]

Sage Live

p.constraints()          # not tested

Or constraint \(0\) only:

Sage

sage: p.constraints(0)         # not tested
(1.0, ([1, 0], [-1.0, 1.0]), 4.0)

Python

>>> from sage.all import *
>>> p.constraints(Integer(0))         # not tested
(1.0, ([1, 0], [-1.0, 1.0]), 4.0)

Sage Live

p.constraints(0)         # not tested

A list of constraints containing only \(1\):

Sage

sage: p.constraints([1])       # not tested
[(1.0, ([2, 0], [-2.0, 1.0]), None)]

Python

>>> from sage.all import *
>>> p.constraints([Integer(1)])       # not tested
[(1.0, ([2, 0], [-2.0, 1.0]), None)]

Sage Live

p.constraints([1])       # not tested

default_variable()[source]¶

Return the default MIPVariable of self.

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: p.default_variable()
MIPVariable with 0 real components

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> p.default_variable()
MIPVariable with 0 real components

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.default_variable()

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

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x, y = p[0], p[1]
p.add_constraint(2*x + 3*y, max=6)
p.add_constraint(3*x + 2*y, max=6)
p.set_objective(x + y + 7)
b = p.get_backend()
b.solver_parameter("simplex_or_intopt", "simplex_only")
b.solver_parameter("verbosity_simplex", "GLP_MSG_ALL")
ans = p.solve()
ans # rel tol 1e-5

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

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[1])
p.get_max(v[1])
p.set_max(v[1],6)
p.get_max(v[1])

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

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])

Python

>>> 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)])

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[1])
p.get_min(v[1])
p.set_min(v[1],6)
p.get_min(v[1])
p.set_min(v[1], None)
p.get_min(v[1])

get_objective_value()[source]¶

Return the value of the objective function.

Note

Behaviour is undefined unless solve has been called before.

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x, y = p[0], p[1]
p.add_constraint(2*x + 3*y, max=6)
p.add_constraint(3*x + 2*y, max=6)
p.set_objective(x + y + 7)
p.solve()  # rel tol 1e-5
p.get_objective_value()  # rel tol 1e-5

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 by get_objective_value() and bestobjective is the value returned by best_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

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

Python

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

Sage Live

# needs sage.graphs
g = graphs.CubeGraph(9)
p = MixedIntegerLinearProgram(solver='GLPK')
p.solver_parameter("mip_gap_tolerance",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)) <= 1)
p.add_constraint(b[v] == 1)  # Force an easy non-0 solution
p.solve() # rel tol 100
p.get_relative_objective_gap()  # random

get_values(convert=None, tolerance=None, *lists)[source]¶

Return values found by the previous call to solve().

INPUT:

*lists – any instance of MIPVariable (or one of its elements), or lists of them
convert – (default: None) ZZ, bool, or True:
- if convert=None (default), return all variable values as the backend provides them, i.e., as an element of base_ring() or a float.
- if convert=ZZ, convert all variable values from the base_ring() by rounding to the nearest integer.
- if convert=bool, convert all variable values from the base_ring() by rounding to 0/1 and converting to bool.
- if convert=True, use ZZ for MIP variables declared integer or binary, and convert the values of all other variables to the base_ring().
tolerance – None, a positive real number, or 0 (if base_ring() is an exact ring). Required if convert is not None and any integer conversion is to be done. If the variable value differs from the nearest integer by more than tolerance, raise a RuntimeError.

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, a float.

For the numerical solvers, base_ring() is RDF, an inexact ring. Code using get_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 and tolerance facilitate writing correct code. See examples below.

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x = p.new_variable(nonnegative=True)
y = p.new_variable(nonnegative=True)
p.set_objective(x[3] + 3*y[2,9] + x[5])
p.add_constraint(x[3] + y[2,9] + 2*x[5], max=2)
p.solve()

To return the value of y[2,9] in the optimal solution:

Sage

sage: p.get_values(y[2,9])
2.0
sage: type(_)
<class 'float'>

Python

>>> from sage.all import *
>>> p.get_values(y[Integer(2),Integer(9)])
2.0
>>> type(_)
<class 'float'>

Sage Live

p.get_values(y[2,9])
type(_)

To convert the value to the base_ring():

Sage

sage: p.get_values(y[2,9], convert=True)
2.0
sage: _.parent()
Real Double Field

Python

>>> from sage.all import *
>>> p.get_values(y[Integer(2),Integer(9)], convert=True)
2.0
>>> _.parent()
Real Double Field

Sage Live

p.get_values(y[2,9], convert=True)
_.parent()

To get a dictionary identical to x containing the values for the corresponding variables in the optimal solution:

Sage

sage: x_sol = p.get_values(x)
sage: sorted(x_sol)
[3, 5]

Python

>>> from sage.all import *
>>> x_sol = p.get_values(x)
>>> sorted(x_sol)
[3, 5]

Sage Live

x_sol = p.get_values(x)
sorted(x_sol)

Obviously, it also works with variables of higher dimension:

Sage

sage: y_sol = p.get_values(y)

Python

>>> from sage.all import *
>>> y_sol = p.get_values(y)

Sage Live

y_sol = p.get_values(y)

We could also have tried

Sage

sage: [x_sol, y_sol] = p.get_values(x, y)

Python

>>> from sage.all import *
>>> [x_sol, y_sol] = p.get_values(x, y)

Sage Live

[x_sol, y_sol] = p.get_values(x, y)

Or:

Sage

sage: [x_sol, y_sol] = p.get_values([x, y])

Python

>>> from sage.all import *
>>> [x_sol, y_sol] = p.get_values([x, y])

Sage Live

[x_sol, y_sol] = p.get_values([x, y])

Using convert and tolerance. First, a binary knapsack:

Sage

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}

Python

>>> 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}

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x = p.new_variable(binary=True)
p.set_objective(3*x[1] + 4*x[2] + 5*x[3])
p.add_constraint(2*x[1] + 3*x[2] + 4*x[3] <= 6)
p.solve()
x_opt = p.get_values(x); x_opt
type(x_opt[1])
x_opt_ZZ = p.get_values(x, convert=True, tolerance=1e-6); x_opt_ZZ
x_opt_ZZ[1].parent()
x_opt_bool = p.get_values(x, convert=bool, tolerance=1e-6); x_opt_bool

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

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}

Python

>>> 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}

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK', maximization=False)
x = p.new_variable(nonnegative=True)
x.set_max(1)
p.add_constraint(x['sa'] + x['sb'] == 1)
p.add_constraint(x['sa'] + x['ba'] - x['ab'] - x['at'] == 0)
p.add_constraint(x['sb'] + x['ab'] - x['ba'] - x['bt'] == 0)
p.set_objective(10*x['sa'] + 10*x['bt'])
p.solve()
x_opt = p.get_values(x); x_opt
x_opt_ZZ = p.get_values(x, convert=ZZ, tolerance=1e-6); x_opt_ZZ

interactive_lp_problem(form='standard')[source]¶

Return an InteractiveLPProblem and, if available, a basis.

INPUT:

form – (default: 'standard') a string specifying return type: either None, or 'std' or 'standard', respectively returns an instance of InteractiveLPProblem or of InteractiveLPProblemStandardForm

OUTPUT:

A 2-tuple consists of an instance of class InteractiveLPProblem or InteractiveLPProblemStandardForm that is constructed based on a given MixedIntegerLinearProgram, and a list of basic variables (the basis) if standard form is chosen (by default), otherwise None.

All variables must have 0 as lower bound and no upper bound.

EXAMPLES:

Sage

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

Python

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

Sage Live

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[0] + x[1] - 7*y[0] + v[0] <= 2, name='K')
p.add_constraint(x[1] + 2*y[0] - v[0] <= 3)
p.add_constraint(5*x[0] + y[0] <= 21, name='L')
p.set_objective(2*x[0] + 3*x[1] + 4*y[0] + 5*v[0])
lp, basis = p.interactive_lp_problem()
basis
lp.constraint_coefficients()
lp.b()
lp.objective_coefficients()
lp.decision_variables()
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 a MIPVariable, but one of its elements)

OUTPUT: True if the variable e is binary; False otherwise

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[1])
p.is_binary(v[1])
p.set_binary(v[1])
p.is_binary(v[1])

is_integer(e)[source]¶

Test whether the variable is an integer. Variables are real by default.

INPUT:

e – a variable (not a MIPVariable, but one of its elements)

OUTPUT: True if the variable e is an integer; False otherwise

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[1])
p.is_integer(v[1])
p.set_integer(v[1])
p.is_integer(v[1])

is_real(e)[source]¶

Test whether the variable is real.

INPUT:

e – a variable (not a MIPVariable, but one of its elements)

OUTPUT: True if the variable is real; False otherwise

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[1])
p.is_real(v[1])
p.set_binary(v[1])
p.is_real(v[1])
p.set_real(v[1])
p.is_real(v[1])

linear_constraints_parent()[source]¶

Return the parent for all linear constraints.

See linear_functions for more details.

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: p.linear_constraints_parent()
Linear constraints over Real Double Field

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> p.linear_constraints_parent()
Linear constraints over Real Double Field

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.linear_constraints_parent()

linear_functions_parent()[source]¶

Return the parent for all linear functions.

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: p.linear_functions_parent()
Linear functions over Real Double Field

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> p.linear_functions_parent()
Linear functions over Real Double Field

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.linear_functions_parent()

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

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: x = p.new_variable(nonnegative=True)

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> x = p.new_variable(nonnegative=True)

Sage Live

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] or x["b"], and has methods items() and keys().

See also

set_min(), get_min() – set/get the lower bound of a variable
set_max(), get_max() – set/get the upper bound of a variable

INPUT:

binary, integer, real – boolean. Set one of these arguments to True 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 type
name – string; associates a name to the variable. This is only useful when exporting the linear program to a file using write_mps or write_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 current MixedIntegerLinearProgram.

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: x = p.new_variable(); x
MIPVariable with 0 real components
sage: x0 = x[0]; x0
x_0

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x = p.new_variable(); x
x0 = x[0]; x0

By default, variables are unbounded:

Sage

sage: print(p.get_min(x0))
None
sage: print(p.get_max(x0))
None

Python

>>> from sage.all import *
>>> print(p.get_min(x0))
None
>>> print(p.get_max(x0))
None

Sage Live

print(p.get_min(x0))
print(p.get_max(x0))

To define two dictionaries of variables, the first being of real type, and the second of integer type

Sage

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

Python

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

Sage Live

x = p.new_variable(real=True, nonnegative=True)
y = p.new_variable(integer=True, nonnegative=True)
p.add_constraint(x[2] + y[3,5], max=2)
p.is_integer(x[2])
p.is_integer(y[3,5])

An exception is raised when two types are supplied

Sage

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

Python

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

Sage Live

z = p.new_variable(real=True, integer=True)

Unbounded variables:

Sage

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)

Python

>>> 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)

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x = p.new_variable(real=True)
y = p.new_variable(integer=True)
p.add_constraint(x[0] + x[3] <= 8)
p.add_constraint(y[0] >= y[1])
p.show()

On the Sage command line, generator syntax is accepted as a shorthand for generating new variables with default settings:

Sage

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)

Python

>>> 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)

Sage Live

mip.<x, y, z> = MixedIntegerLinearProgram(solver='GLPK')
mip.add_constraint(x[0] + y[1] + z[2] <= 10)
mip.show()

number_of_constraints()[source]¶

Return the number of constraints assigned so far.

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.add_constraint(p[0] - p[2], min=1, max=4)
p.add_constraint(p[0] - 2*p[1], min=1)
p.number_of_constraints()

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

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.add_constraint(p[0] - p[2], max=4)
p.number_of_variables()
p.add_constraint(p[0] - 2*p[1], min=1)
p.number_of_variables()
p = MixedIntegerLinearProgram(solver='glpk')
p.add_constraint(p[0] - p[2], min=1, max=4)
p.number_of_variables()
p = MixedIntegerLinearProgram(solver='gurobi')   # optional - Gurobi
p.add_constraint(p[0] - p[2], min=1, max=4)      # optional - Gurobi
p.number_of_variables()                          # optional - Gurobi

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 of self.

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 type lower_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 of show(). Just in case.

See also

to_linear_program() – return the MixedIntegerLinearProgram object associated with a Polyhedron() object.

EXAMPLES:

A LP on two variables:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.add_constraint(0 <= 2*p['x'] + p['y'] <= 1)
p.add_constraint(0 <= 3*p['y'] + p['x'] <= 2)
P = p.polyhedron(); P

3-D Polyhedron:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.add_constraint(0 <= 2*p['x'] + p['y'] + 3*p['z'] <= 1)
p.add_constraint(0 <= 2*p['y'] + p['z'] + 3*p['x'] <= 1)
p.add_constraint(0 <= 2*p['z'] + p['x'] + 3*p['y'] <= 1)
P = p.polyhedron(); P

An empty polyhedron:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.add_constraint(2*v['x'] + v['y'] + 3*v['z'] <= 1)
p.add_constraint(2*v['y'] + v['z'] + 3*v['x'] <= 1)
p.add_constraint(2*v['z'] + v['x'] + 3*v['y'] >= 2)
P = p.polyhedron(); P

An unbounded polyhedron:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.add_constraint(2*p['x'] + p['y'] - p['z'] <= 1)
P = p.polyhedron(); P

A square (see Issue #14395)

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x,y = p['x'], p['y']
p.add_constraint(x <= 1)
p.add_constraint(x >= -1)
p.add_constraint(y <= 1)
p.add_constraint(y >= -1)
p.polyhedron()

We can also use a backend that supports exact arithmetic:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='PPL')
x,y = p['x'], p['y']
p.add_constraint(x <= 1)
p.add_constraint(x >= -1)
p.add_constraint(y <= 1)
p.add_constraint(y >= -1)
p.polyhedron()

remove_constraint(i)[source]¶

Removes a constraint from self.

INPUT:

i – index of the constraint to remove

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x, y = p[0], p[1]
p.add_constraint(x + y, max=10)
p.add_constraint(x - y, max=0)
p.add_constraint(x, max=4)
p.show()
p.remove_constraint(1)
p.show()
p.number_of_constraints()

remove_constraints(constraints)[source]¶

Remove several constraints.

INPUT:

constraints – an iterable containing the indices of the rows to remove

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x, y = p[0], p[1]
p.add_constraint(x + y, max=10)
p.add_constraint(x - y, max=0)
p.add_constraint(x, max=4)
p.show()
p.remove_constraints([0, 1])
p.show()
p.number_of_constraints()

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

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(check_redundant=True, solver='GLPK')
x, y = p[0], p[1]
p.add_constraint(x + y, max=10)
for each in range(10):
    p.add_constraint(x - y, max=10)
p.add_constraint(x, max=4)
p.number_of_constraints()
p.remove_constraints(range(1, 9))
p.remove_constraint(1)
p.number_of_constraints()

We should now be able to add the old constraint back in:

Sage

sage: for each in range(10):
....:     p.add_constraint(x - y, max=10)
sage: p.number_of_constraints()
3

Python

>>> from sage.all import *
>>> for each in range(Integer(10)):
...     p.add_constraint(x - y, max=Integer(10))
>>> p.number_of_constraints()
3

Sage Live

for each in range(10):
    p.add_constraint(x - y, max=10)
p.number_of_constraints()

set_binary(ee)[source]¶

Set a variable or a MIPVariable as binary.

INPUT:

ee – an instance of MIPVariable or one of its elements

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: x = p.new_variable(nonnegative=True)

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> x = p.new_variable(nonnegative=True)

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x = p.new_variable(nonnegative=True)

With the following instruction, all the variables from x will be binary:

Sage

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)

Python

>>> 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))

Sage Live

p.set_binary(x)
p.set_objective(x[0] + x[1])
p.add_constraint(-3*x[0] + 2*x[1], max=2)

It is still possible, though, to set one of these variables as integer while keeping the others as they are:

Sage

sage: p.set_integer(x[3])

Python

>>> from sage.all import *
>>> p.set_integer(x[Integer(3)])

Sage Live

p.set_integer(x[3])

set_integer(ee)[source]¶

Set a variable or a MIPVariable as integer.

INPUT:

ee – an instance of MIPVariable or one of its elements

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: x = p.new_variable(nonnegative=True)

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> x = p.new_variable(nonnegative=True)

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x = p.new_variable(nonnegative=True)

With the following instruction, all the variables from x will be integers:

Sage

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)

Python

>>> 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))

Sage Live

p.set_integer(x)
p.set_objective(x[0] + x[1])
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

sage: p.set_binary(x[3])

Python

>>> from sage.all import *
>>> p.set_binary(x[Integer(3)])

Sage Live

p.set_binary(x[3])

set_max(v, max)[source]¶

Set the maximum value of a variable.

INPUT:

v – a variable
max – the maximum value the variable can take; when max=None, the variable has no upper bound

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[1])
p.get_max(v[1])
p.set_max(v[1],6)
p.get_max(v[1])

With a MIPVariable as an argument:

Sage

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

Python

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

Sage Live

vv = p.new_variable(real=True)
p.get_max(vv)
p.get_max(vv[0])
p.set_max(vv,5)
p.get_max(vv[0])
p.get_max(vv[9])

set_min(v, min)[source]¶

Set the minimum value of a variable.

INPUT:

v – a variable
min – the minimum value the variable can take; when min=None, the variable has no lower bound

See also

get_min() – get the minimum value of a variable

EXAMPLES:

Sage

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])

Python

>>> 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)])

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)
p.set_objective(v[1])
p.get_min(v[1])
p.set_min(v[1],6)
p.get_min(v[1])
p.set_min(v[1], None)
p.get_min(v[1])

With a MIPVariable as an argument:

Sage

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

Python

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

Sage Live

vv = p.new_variable(real=True)
p.get_min(vv)
p.get_min(vv[0])
p.set_min(vv,5)
p.get_min(vv[0])
p.get_min(vv[9])

set_objective(obj)[source]¶

Set the objective of the MixedIntegerLinearProgram.

INPUT:

obj – a linear function to be optimized ( can also be set to None or 0 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

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()

Python

>>> 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()

Sage Live

p = MixedIntegerLinearProgram(maximization=True, solver='GLPK')
x = p.new_variable(nonnegative=True)
p.set_objective(x[1] + 5*x[2])
p.add_constraint(x[1] + 2/10*x[2], max=4)
p.add_constraint(1.5*x[1] + 3*x[2], max=4)
round(p.solve(),5)
p.set_objective(None)
_ = p.solve()

set_problem_name(name)[source]¶

Set the name of the MixedIntegerLinearProgram.

INPUT:

name – string representing the name of the MixedIntegerLinearProgram

EXAMPLES:

Sage

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)

Python

>>> 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)

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.set_problem_name("Test program")
p

set_real(ee)[source]¶

Set a variable or a MIPVariable as real.

INPUT:

ee – an instance of MIPVariable or one of its elements

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: x = p.new_variable(nonnegative=True)

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> x = p.new_variable(nonnegative=True)

Sage Live

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

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)

Python

>>> 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)

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x = p.new_variable(name='Hey')
p.set_objective(x[1] + x[2])
p.add_constraint(-3*x[1] + 2*x[2], max=2, name='Constraint_1')
p.show()

Without any names

Sage

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)

Python

>>> 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)

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x = p.new_variable(nonnegative=True)
p.set_objective(x[1] + x[2])
p.add_constraint(-3*x[1] + 2*x[2], max=2)
p.show()

With \(\QQ\) coefficients:

Sage

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)

Python

>>> 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)

Sage Live

p = MixedIntegerLinearProgram(solver='ppl')
x = p.new_variable(nonnegative=True)
p.set_objective(x[1] + 1/2*x[2])
p.add_constraint(-3/5*x[1] + 2/7*x[2], max=2/5)
p.show()

With a constant term in the objective:

Sage

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)

Python

>>> 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)

Sage Live

p = MixedIntegerLinearProgram(solver='ppl')
x = p.new_variable(nonnegative=True)
p.set_objective(x[0] + 42)
p.show()

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() and set_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

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x, y = p[0], p[1]
p.add_constraint(2*x + 3*y, max=6)
p.add_constraint(3*x + 2*y, max=6)
p.set_objective(x + y + 7)
p.set_integer(x); p.set_integer(y)
p.solve()

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

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: p.solver_parameter("timelimit", 60)

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> p.solver_parameter("timelimit", Integer(60))

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.solver_parameter("timelimit", 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

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")
''

Python

>>> 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")
''

Sage Live

# optional - cplex
p = MixedIntegerLinearProgram(solver='CPLEX')
p.solver_parameter("logfile")
p.solver_parameter("logfile", "/dev/null")
p.solver_parameter("logfile")
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
sage: p = MixedIntegerLinearProgram(solver='CPLEX')   # optional - CPLEX
sage: p.solver_parameter("CPX_PARAM_TILIM", 60)       # optional - CPLEX
Python
>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='CPLEX')   # optional - CPLEX
>>> p.solver_parameter("CPX_PARAM_TILIM", Integer(60))       # optional - CPLEX
Sage Live
p = MixedIntegerLinearProgram(solver='CPLEX')   # optional - CPLEX
p.solver_parameter("CPX_PARAM_TILIM", 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 parameter
value – the parameter’s value if it is to be defined, or None (default) to obtain its current value

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: p.solver_parameter("timelimit", 60)
sage: p.solver_parameter("timelimit")
60.0

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> p.solver_parameter("timelimit", Integer(60))
>>> p.solver_parameter("timelimit")
60.0

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
p.solver_parameter("timelimit", 60)
p.solver_parameter("timelimit")

sum(L)[source]¶

Efficiently compute the sum of a sequence of LinearFunction elements

INPUT:

mip – the MixedIntegerLinearProgram parent
L – list of LinearFunction instances

Note

The use of the regular sum function is not recommended as it is much less efficient than this one

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: v = p.new_variable(nonnegative=True)

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='GLPK')
>>> v = p.new_variable(nonnegative=True)

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
v = p.new_variable(nonnegative=True)

The following command:

Sage

sage: s = p.sum(v[i] for i in range(90))

Python

>>> from sage.all import *
>>> s = p.sum(v[i] for i in range(Integer(90)))

Sage Live

s = p.sum(v[i] for i in range(90))

is much more efficient than:

Sage

sage: s = sum(v[i] for i in range(90))

Python

>>> from sage.all import *
>>> s = sum(v[i] for i in range(Integer(90)))

Sage Live

s = sum(v[i] for i in range(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

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x = p.new_variable(nonnegative=True)
p.set_objective(x[1] + x[2])
p.add_constraint(-3*x[1] + 2*x[2], max=2)
import tempfile
with tempfile.NamedTemporaryFile(suffix='.lp') as f:
    p.write_lp(f.name)

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 written
modern – lets you choose between Fixed MPS and Free MPS:
- True – outputs the problem in Free MPS
- False – outputs the problem in Fixed MPS

EXAMPLES:

Sage

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

Python

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

Sage Live

p = MixedIntegerLinearProgram(solver='GLPK')
x = p.new_variable(nonnegative=True)
p.set_objective(x[1] + x[2])
p.add_constraint(-3*x[1] + 2*x[2], max=2, name='OneConstraint')
import tempfile
with tempfile.NamedTemporaryFile(suffix='.mps') as f:
    p.write_mps(f.name)

For information about the MPS file format, see Wikipedia article MPS_(format)