Mixed Integer Linear Programming
A linear program (LP) is an optimization problem in the following form
with given ,
,
and unknown
.
If some or all variables in the vector
are restricted over
the integers
, 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.
Imagine you want to solve the following linear system of three equations:
and this additional inequality:
where all . You know that the trivial solution is
,
but what is the first non-trivial one with
?
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 an dictionary w of integer variables w via w = p.new_variable(integer=True) (note that by default all variables are non-negative, cf new_variable()).
- Add those three equations as equality constraints via add_constraint.
- Also add the inequality constraint.
- Add an inequality constraint
to exclude the trivial solution.
- By default, all variables are non-negative. We remove that constraint via p.set_min(variable, None), see set_min.
- Specify the objective function via set_objective. In our case that is just
. 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: 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_min(w[i], None) for i in range(1,4) ]
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=-oo, max=+oo)
x_2 is an integer variable (min=-oo, max=+oo)
x_3 is an integer variable (min=-oo, max=+oo)
sage: print 'Objective Value:', p.solve()
Objective Value: 2.0
sage: for i, v in p.get_values(w).iteritems():\
print 'w_%s = %s' % (i, int(round(v)))
w_0 = 15
w_1 = 10
w_2 = 3
w_3 = 2
Different backends compute with different base fields, for example:
sage: p = MixedIntegerLinearProgram(solver = 'GLPK')
sage: p.base_ring()
Real Double Field
sage: x = p.new_variable(real=True, nonnegative=True)
sage: 0.5 + 3/2*x[1]
0.5 + 1.5*x_0
sage: p = MixedIntegerLinearProgram(solver = 'ppl')
sage: p.base_ring()
Rational Field
sage: x = p.new_variable(nonnegative=True)
sage: 0.5 + 3/2*x[1]
1/2 + 3/2*x_0
AUTHORS:
Below are listed the methods of MixedIntegerLinearProgram. This module also implements the MIPSolverException exception, as well as the MIPVariable class.
add_constraint() | Adds a constraint to the MixedIntegerLinearProgram |
base_ring() | Return the base ring |
constraints() | Returns a list of constraints, as 3-tuples |
get_backend() | Returns the backend instance used |
get_max() | Returns the maximum value of a variable |
get_min() | Returns the minimum value of a variable |
get_values() | Return values found by the previous call to solve() |
is_binary() | Tests whether the variable e is binary |
is_integer() | Tests whether the variable is an integer |
is_real() | Tests whether the variable is real |
linear_constraints_parent() | Return the parent for all linear constraints |
linear_function() | Construct a new linear function |
linear_functions_parent() | Return the parent for all linear functions |
new_variable() | Returns an instance of MIPVariable associated |
number_of_constraints() | Returns the number of constraints assigned so far |
number_of_variables() | Returns the number of variables used so far |
polyhedron() | Returns the polyhedron defined by the Linear Program |
remove_constraint() | Removes a constraint from self |
remove_constraints() | Remove several constraints |
set_binary() | Sets a variable or a MIPVariable as binary |
set_integer() | Sets a variable or a MIPVariable as integer |
set_max() | Sets the maximum value of a variable |
set_min() | Sets the minimum value of a variable |
set_objective() | Sets the objective of the MixedIntegerLinearProgram |
set_problem_name() | Sets the name of the MixedIntegerLinearProgram |
set_real() | Sets a variable or a MIPVariable as real |
show() | Displays the MixedIntegerLinearProgram in a human-readable |
solve() | Solves 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 |
Bases: exceptions.RuntimeError
Exception raised when the solver fails.
Bases: sage.structure.sage_object.SageObject
MIPVariable is a variable used by the class MixedIntegerLinearProgram.
Returns the current variable’s depth.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable(nonnegative=True)
sage: p.set_objective(v[0] + v[1])
sage: v.depth()
1
Returns the pairs (keys,value) contained in the dictionary.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable(nonnegative=True)
sage: p.set_objective(v[0] + v[1])
sage: v.items()
[(0, x_0), (1, x_1)]
Returns the keys already defined in the dictionary.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable(nonnegative=True)
sage: p.set_objective(v[0] + v[1])
sage: v.keys()
[0, 1]
Sets an upper bound on the variable.
INPUT:
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable(real=True, nonnegative=True, dim=2)
sage: p.get_max(v)
sage: p.get_max(v[0])
sage: p.get_max(v[0][0])
sage: p.set_max(v,4)
sage: p.get_max(v)
4
sage: p.get_max(v[0])
4
sage: p.get_max(v[0][0])
4.0
Sets a lower bound on the variable.
INPUT:
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable(real=True, nonnegative=True, dim=2)
sage: p.get_min(v)
0
sage: p.get_min(v[0])
0
sage: p.get_min(v[0][0])
0.0
sage: p.set_min(v,4)
sage: p.get_min(v)
4
sage: p.get_min(v[0])
4
sage: p.get_min(v[0][0])
4.0
Returns the symbolic variables associated to the current dictionary.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable(nonnegative=True)
sage: p.set_objective(v[0] + v[1])
sage: v.values()
[x_0, x_1]
Bases: sage.structure.sage_object.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 Wikipedia article Linear_programming for further information on linear programming, and the MILP module for its use in Sage.
INPUT:
solver – selects a solver:
GLPK (solver="GLPK"). See the GLPK web site.
COIN Branch and Cut (solver="Coin"). See the COIN-OR web site.
CPLEX (solver="CPLEX"). See the CPLEX web site.
web site.
web site.
web site.
If solver=None (default), the default solver is used (see default_mip_solver())
maximization
constraint_generation – Only used when solver=None.
Warning
All LP variables are non-negative by default (see new_variable() and set_min()).
See also
EXAMPLES:
Computation of a maximum stable set in Petersen’s graph:
sage: g = graphs.PetersenGraph()
sage: p = MixedIntegerLinearProgram(maximization=True)
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(labels=None):
....: p.add_constraint(b[u] + b[v], max=1)
sage: p.solve(objective_only=True)
4.0
TESTS:
Check that trac ticket #16497 is fixed:
sage: from sage.numerical.mip import MixedIntegerLinearProgram
sage: for type in ["binary", "integer"]:
....: k = 3
....: items = [1/5, 1/3, 2/3, 3/4, 5/7]
....: maximum=1
....: p=MixedIntegerLinearProgram()
....: box=p.new_variable(nonnegative=True, **{type:True})
....: for b in range(k):
....: p.add_constraint(p.sum([items[i]*box[i,b] for i in range(len(items))]) <= maximum)
....: for i in range(len(items)):
....: p.add_constraint(p.sum([box[i,b] for b in range(k)]) == 1)
....: p.set_objective(None)
....: _ = p.solve()
....: box=p.get_values(box)
....: print(all(v in ZZ for v in box.values()))
True
True
Adds a constraint to the MixedIntegerLinearProgram.
INPUT:
max – An upper bound on the constraint (set to None by default). This must be a numerical value.
min – A lower bound on the constraint. This must be a numerical value.
name – A name for the constraint.
To set a lower and/or upper bound on the variables use the methods set_min and/or set_max of MixedIntegerLinearProgram.
EXAMPLE:
Consider the following linear program:
Maximize:
x + 5 * y
Constraints:
x + 0.2 y <= 4
1.5 * x + 3 * y <= 4
Variables:
x is Real (min = 0, max = None)
y is Real (min = 0, max = None)
It can be solved as follows:
sage: p = MixedIntegerLinearProgram(maximization=True)
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
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: 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: p.add_constraint( x[5] + 3*x[7] - x[6], max = 3 )
One can also define double-bounds or equality using symbols <=, >= and ==:
sage: p.add_constraint( x[5] + 3*x[7] == x[6] + 3 )
sage: p.add_constraint( x[5] + 3*x[7] <= x[6] + 3 <= x[8] + 27 )
The previous program can be rewritten:
sage: p = MixedIntegerLinearProgram(maximization=True)
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] <= 4)
sage: p.add_constraint(1.5*x[1] + 3*x[2] <= 4)
sage: round(p.solve(), 5)
6.66667
TESTS:
Complex constraints:
sage: p = MixedIntegerLinearProgram(solver = "GLPK")
sage: b = p.new_variable(nonnegative=True)
sage: p.add_constraint( b[8] - b[15] <= 3*b[8] + 9)
sage: p.show()
Maximization:
Constraints:
-2.0 x_0 - x_1 <= 9.0
Variables:
x_0 is a continuous variable (min=0.0, max=+oo)
x_1 is a continuous variable (min=0.0, max=+oo)
Empty constraint:
sage: p=MixedIntegerLinearProgram()
sage: p.add_constraint(sum([]),min=2)
Min/Max are numerical
sage: v = p.new_variable(nonnegative=True)
sage: p.add_constraint(v[3] + v[5], min = v[6])
Traceback (most recent call last):
...
ValueError: min and max arguments are required to be numerical
sage: p.add_constraint(v[3] + v[5], max = v[6])
Traceback (most recent call last):
...
ValueError: min and max arguments are required to be numerical
Do not add redundant elements (notice only one copy of each constraint is added):
sage: lp = MixedIntegerLinearProgram(solver = "GLPK", check_redundant=True)
sage: for each in xrange(10): lp.add_constraint(lp[0]-lp[1],min=1)
sage: lp.show()
Maximization:
Constraints:
1.0 <= x_0 - x_1
Variables:
x_0 is a continuous variable (min=0.0, max=+oo)
x_1 is a continuous variable (min=0.0, max=+oo)
We check for constant multiples of constraints as well:
sage: for each in xrange(10): lp.add_constraint(2*lp[0]-2*lp[1],min=2)
sage: lp.show()
Maximization:
Constraints:
1.0 <= x_0 - x_1
Variables:
x_0 is a continuous variable (min=0.0, max=+oo)
x_1 is a continuous variable (min=0.0, max=+oo)
But if the constant multiple is negative, we should add it anyway (once):
sage: for each in xrange(10): lp.add_constraint(-2*lp[0]+2*lp[1],min=-2)
sage: lp.show()
Maximization:
Constraints:
1.0 <= x_0 - x_1
x_0 - x_1 <= 1.0
Variables:
x_0 is a continuous variable (min=0.0, max=+oo)
x_1 is a continuous variable (min=0.0, max=+oo)
TESTS:
Catch True / False as INPUT (trac ticket #13646):
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable(nonnegative=True)
sage: p.add_constraint(True)
Traceback (most recent call last):
...
ValueError: argument must be a linear function or constraint, got True
Return the base ring.
OUTPUT:
A ring. The coefficients that the chosen solver supports.
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver='GLPK')
sage: p.base_ring()
Real Double Field
sage: p = MixedIntegerLinearProgram(solver='ppl')
sage: p.base_ring()
Rational Field
Returns 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
, the method returns constraint
.
- 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 to all the
others.
lower_bound and upper_bound are numerical values.
EXAMPLE:
First, let us define a small LP:
sage: p = MixedIntegerLinearProgram()
sage: p.add_constraint(p[0] - p[2], min = 1, max = 4)
sage: p.add_constraint(p[0] - 2*p[1], min = 1)
To obtain the list of all constraints:
sage: p.constraints() # not tested
[(1.0, ([1, 0], [-1.0, 1.0]), 4.0), (1.0, ([2, 0], [-2.0, 1.0]), None)]
Or constraint only:
sage: p.constraints(0) # not tested
(1.0, ([1, 0], [-1.0, 1.0]), 4.0)
A list of constraints containing only :
sage: p.constraints([1]) # not tested
[(1.0, ([2, 0], [-2.0, 1.0]), None)]
TESTS:
As the ordering of the variables in each constraint depends on the solver used, we define a short function reordering it before it is printed. The output would look the same without this function applied:
sage: def reorder_constraint((lb,(ind,coef),ub)):
... d = dict(zip(ind, coef))
... ind.sort()
... return (lb, (ind, [d[i] for i in ind]), ub)
Running the examples from above, reordering applied:
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: sorted(map(reorder_constraint,p.constraints()))
[(1.0, ([0, 1], [1.0, -1.0]), 4.0), (1.0, ([0, 2], [1.0, -2.0]), None)]
sage: reorder_constraint(p.constraints(0))
(1.0, ([0, 1], [1.0, -1.0]), 4.0)
sage: sorted(map(reorder_constraint,p.constraints([1])))
[(1.0, ([0, 2], [1.0, -2.0]), None)]
Returns the backend instance used.
This might be useful when acces to additional functions provided by the backend is needed.
EXAMPLE:
This example uses the simplex algorthm and prints information:
sage: p = MixedIntegerLinearProgram(solver="GLPK")
sage: x, y = p[0], p[1]
sage: p.add_constraint(2*x + 3*y, max = 6)
sage: p.add_constraint(3*x + 2*y, max = 6)
sage: p.set_objective(x + y + 7)
sage: b = p.get_backend()
sage: b.solver_parameter("simplex_or_intopt", "simplex_only")
sage: b.solver_parameter("verbosity_simplex", "GLP_MSG_ALL")
sage: p.solve() # tol 0.00001
GLPK Simplex Optimizer, v4.44
2 rows, 2 columns, 4 non-zeros
* 0: obj = 7.000000000e+00 infeas = 0.000e+00 (0)
* 2: obj = 9.400000000e+00 infeas = 0.000e+00 (0)
OPTIMAL SOLUTION FOUND
9.4
Returns the maximum value of a variable.
INPUT:
OUTPUT:
Maximum value of the variable, or None if the variable has no upper bound.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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
Returns the minimum value of a variable.
INPUT:
OUTPUT:
Minimum value of the variable, or None if the variable has no lower bound.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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])
Return values found by the previous call to solve().
INPUT:
OUTPUT:
Note
While a variable may be declared as binary or integer, its value as returned by the solver is of type float.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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
To return the optimal value of y[2,9]:
sage: p.get_values(y[2,9])
2.0
To get a dictionary identical to x containing optimal values for the corresponding variables
sage: x_sol = p.get_values(x)
sage: x_sol.keys()
[3, 5]
Obviously, it also works with variables of higher dimension:
sage: y_sol = p.get_values(y)
We could also have tried
sage: [x_sol, y_sol] = p.get_values(x, y)
Or:
sage: [x_sol, y_sol] = p.get_values([x, y])
TESTS:
When ‘dim’ will be removed, also remove from this function the code that uses it:
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable(dim=2)
doctest:...: DeprecationWarning: The 'dim' argument will soon disappear. Fortunately variable[1,2] is easier to use than variable[1][2]
See http://trac.sagemath.org/15489 for details.
sage: p.add_constraint(b[1][2] + b[2][3] == 0)
sage: _ = p.solve()
sage: _ = p.get_values(b)
Tests whether the variable e is binary. Variables are real by default.
INPUT:
OUTPUT:
True if the variable e is binary; False otherwise.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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
Tests whether the variable is an integer. Variables are real by default.
INPUT:
OUTPUT:
True if the variable e is an integer; False otherwise.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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
Tests whether the variable is real.
INPUT:
OUTPUT:
True if the variable is real; False otherwise.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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
Return the parent for all linear constraints
See linear_functions for more details.
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: p.linear_constraints_parent()
Linear constraints over Real Double Field
Construct a new linear function
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: p.linear_function({1:3, 4:5})
3*x_1 + 5*x_4
This is equivalent to:
sage: p({1:3, 4:5})
3*x_1 + 5*x_4
Return the parent for all linear functions
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: p.linear_functions_parent()
Linear functions over Real Double Field
Returns an instance of MIPVariable associated to the current instance of MixedIntegerLinearProgram.
A new variable x is defined by:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable(nonnegative=True)
It behaves exactly as an usual dictionary would. It can use any key argument you may like, as x[5] or x["b"], and has methods items() and keys().
INPUT:
See also
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
To define two dictionaries of variables, the first being
of real type, and the second of integer type ::
sage: x = p.new_variable(real=True, nonnegative=True)
sage: y = p.new_variable(integer=True, nonnegative=True)
sage: p.add_constraint(x[2] + y[3,5], max=2)
sage: p.is_integer(x[2])
False
sage: p.is_integer(y[3,5])
True
An exception is raised when two types are supplied
sage: z = p.new_variable(real = True, integer = True)
Traceback (most recent call last):
...
ValueError: Exactly one of the available types has to be True
Unbounded variables:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable(real=True, nonnegative=False)
sage: y = p.new_variable(integer=True, nonnegative=False)
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)
TESTS:
Default behaviour (trac ticket #15521):
sage: x = p.new_variable(nonnegative=True)
sage: p.get_min(x[0])
0.0
Returns the number of constraints assigned so far.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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
Returns 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 , with
, into
equations, by adding extra variables:
,
.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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
Returns 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 -th variable represents the
-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 explicitely 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.
EXAMPLES:
A LP on two variables:
sage: p = MixedIntegerLinearProgram()
sage: p.add_constraint(2*p['x'] + p['y'] <= 1)
sage: p.add_constraint(3*p['y'] + p['x'] <= 2)
sage: P = p.polyhedron(); P
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
3-D Polyhedron:
sage: p = MixedIntegerLinearProgram()
sage: p.add_constraint(2*p['x'] + p['y'] + 3*p['z'] <= 1)
sage: p.add_constraint(2*p['y'] + p['z'] + 3*p['x'] <= 1)
sage: p.add_constraint(2*p['z'] + p['x'] + 3*p['y'] <= 1)
sage: P = p.polyhedron(); P
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 8 vertices
An empty polyhedron:
sage: p = MixedIntegerLinearProgram()
sage: p.add_constraint(2*p['x'] + p['y'] + 3*p['z'] <= 1)
sage: p.add_constraint(2*p['y'] + p['z'] + 3*p['x'] <= 1)
sage: p.add_constraint(2*p['z'] + p['x'] + 3*p['y'] >= 2)
sage: P = p.polyhedron(); P
The empty polyhedron in QQ^3
An unbounded polyhedron:
sage: p = MixedIntegerLinearProgram()
sage: p.add_constraint(2*p['x'] + p['y'] - p['z'] <= 1)
sage: P = p.polyhedron(); P
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 3 vertices and 3 rays
A square (see trac ticket #14395)
sage: p = MixedIntegerLinearProgram()
sage: x,y = p['x'], p['y']
sage: p.set_min(x,None)
sage: p.set_min(y,None)
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
Removes a constraint from self.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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
Remove several constraints.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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
When checking for redundant constraints, make sure you remove only the constraints that were actually added. Problems could arise if you have a function that builds lps non-interactively, but it fails to check whether adding a constraint actually increases the number of constraints. The function might later try to remove constraints that are not actually there:
sage: p = MixedIntegerLinearProgram(check_redundant=True)
sage: x, y = p[0], p[1]
sage: p.add_constraint(x + y, max = 10)
sage: for each in xrange(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
We should now be able to add the old constraint back in:
sage: for each in xrange(10): p.add_constraint(x - y, max = 10)
sage: p.number_of_constraints()
3
Sets a variable or a MIPVariable as binary.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable(nonnegative=True)
With the following instruction, all the variables from x will be binary:
sage: p.set_binary(x)
sage: p.set_objective(x[0] + x[1])
sage: p.add_constraint(-3*x[0] + 2*x[1], max=2)
It is still possible, though, to set one of these variables as integer while keeping the others as they are:
sage: p.set_integer(x[3])
TESTS:
When ‘dim’ will be removed, also remove all the is_* and set_* functions the code that uses it:
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable(dim=2)
sage: p.add_constraint(b[1][2] + b[2][3] == 0)
sage: p.set_binary(b)
Sets a variable or a MIPVariable as integer.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable(nonnegative=True)
With the following instruction, all the variables from x will be integers:
sage: p.set_integer(x)
sage: p.set_objective(x[0] + x[1])
sage: p.add_constraint(-3*x[0] + 2*x[1], max=2)
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])
Sets the maximum value of a variable.
INPUT
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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
With a MIPVariable as an argument:
sage: vv = p.new_variable(real=True, nonnegative=False)
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
Sets the minimum value of a variable.
INPUT:
See also
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
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])
With a MIPVariable as an argument:
sage: vv = p.new_variable(real=True, nonnegative=False)
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
Sets the objective of the MixedIntegerLinearProgram.
INPUT:
EXAMPLE:
Let’s solve the following linear program:
Maximize:
x + 5 * y
Constraints:
x + 0.2 y <= 4
1.5 * x + 3 * y <= 4
Variables:
x is Real (min = 0, max = None)
y is Real (min = 0, max = None)
This linear program can be solved as follows:
sage: p = MixedIntegerLinearProgram(maximization=True)
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()
Sets the name of the MixedIntegerLinearProgram.
INPUT:
EXAMPLE:
sage: p=MixedIntegerLinearProgram()
sage: p.set_problem_name("Test program")
sage: p
Mixed Integer Program "Test program" ( maximization, 0 variables, 0 constraints )
Sets a variable or a MIPVariable as real.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: 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])
Displays the MixedIntegerLinearProgram in a human-readable way.
EXAMPLES:
When constraints and variables have names
sage: p = MixedIntegerLinearProgram(solver = "GLPK")
sage: x = p.new_variable(name="Hey")
sage: p.set_objective(x[1] + x[2])
sage: p.add_constraint(-3*x[1] + 2*x[2], max=2, name="Constraint_1")
sage: p.show()
Maximization:
Hey[1] + Hey[2]
Constraints:
Constraint_1: -3.0 Hey[1] + 2.0 Hey[2] <= 2.0
Variables:
Hey[1] is a continuous variable (min=0.0, max=+oo)
Hey[2] is a continuous variable (min=0.0, max=+oo)
Without any names
sage: p = MixedIntegerLinearProgram(solver = "GLPK")
sage: x = p.new_variable(nonnegative=True)
sage: p.set_objective(x[1] + x[2])
sage: p.add_constraint(-3*x[1] + 2*x[2], max=2)
sage: p.show()
Maximization:
x_0 + x_1
Constraints:
-3.0 x_0 + 2.0 x_1 <= 2.0
Variables:
x_0 is a continuous variable (min=0.0, max=+oo)
x_1 is a continuous variable (min=0.0, max=+oo)
With coefficients:
sage: p = MixedIntegerLinearProgram(solver= 'ppl')
sage: x = p.new_variable(nonnegative=True)
sage: p.set_objective(x[1] + 1/2*x[2])
sage: p.add_constraint(-3/5*x[1] + 2/7*x[2], max=2/5)
sage: p.show()
Maximization:
x_0 + 1/2 x_1
Constraints:
constraint_0: -3/5 x_0 + 2/7 x_1 <= 2/5
Variables:
x_0 is a continuous variable (min=0, max=+oo)
x_1 is a continuous variable (min=0, max=+oo)
Solves the MixedIntegerLinearProgram.
INPUT:
OUTPUT:
The optimal value taken by the objective function.
Warning
By default, all variables of a LP are assumed to be non-negative. See set_min() 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)
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)
0.0
sage: round(x[2],6)
1.333333
Computation of a maximum stable set in Petersen's graph::
sage: g = graphs.PetersenGraph()
sage: p = MixedIntegerLinearProgram(maximization=True)
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(labels=None):
... p.add_constraint(b[u] + b[v], max=1)
sage: p.set_binary(b)
sage: p.solve(objective_only=True)
4.0
Constraints in the objective function are respected:
sage: p = MixedIntegerLinearProgram()
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
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 use GLPK).
Aliases:
Very common parameters have aliases making them solver-independent. For example, the following:
sage: p = MixedIntegerLinearProgram(solver = "GLPK")
sage: p.solver_parameter("timelimit", 60)
Sets the solver to stop its computations after 60 seconds, and works with GLPK, CPLEX and Gurobi.
- "timelimit" – defines the maximum time spent on a computation. Measured in seconds.
Solver-specific parameters:
GLPK : We have implemented very close to comprehensive coverage of the GLPK solver parameters for the simplex and integer optimization methods. For details, see the documentation of GLPKBackend.solver_parameter.
CPLEX’s parameters are identified by a string. Their list is available on ILOG’s website.
The command
sage: p = MixedIntegerLinearProgram(solver = "CPLEX") # optional - CPLEX sage: p.solver_parameter("CPX_PARAM_TILIM", 60) # optional - CPLEXworks 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.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram(solver = "GLPK")
sage: p.solver_parameter("timelimit", 60)
sage: p.solver_parameter("timelimit")
60.0
Efficiently computes the sum of a sequence of LinearFunction elements
INPUT:
Note
The use of the regular sum function is not recommended as it is much less efficient than this one
EXAMPLES:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable(nonnegative=True)
The following command:
sage: s = p.sum([v[i] for i in xrange(90)])
is much more efficient than:
sage: s = sum([v[i] for i in xrange(90)])
Write the linear program as a LP file.
This function export the problem as a LP file.
INPUT:
EXAMPLE:
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.write_lp(os.path.join(SAGE_TMP, "lp_problem.lp"))
Writing problem data to ...
9 lines were written
For more information about the LP file format : http://lpsolve.sourceforge.net/5.5/lp-format.htm
Write 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
EXAMPLE:
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: p.write_mps(os.path.join(SAGE_TMP, "lp_problem.mps"))
Writing problem data to ...
17 records were written
For information about the MPS file format : http://en.wikipedia.org/wiki/MPS_%28format%29
Only for legacy support, use MixedIntegerLinearProgram.sum() instead.
EXAMPLES:
sage: from sage.numerical.mip import Sum
sage: Sum([])
doctest:...: DeprecationWarning: use MixedIntegerLinearProgram.sum() instead
See http://trac.sagemath.org/13646 for details.
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable(nonnegative=True)
sage: Sum([ x[0]+x[1], x[1]+x[2], x[2]+x[3] ]) # deprecation is only shown once
x_0 + 2*x_1 + 2*x_2 + x_3