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 a variable vector w via w = p.new_variable(integer=True) and tell the system that it is over the integers.
- 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 have a minimum of
. 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)
sage: w = p.new_variable(integer=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
A class to represent formal Linear Constraints.
A Linear Constraint being an inequality between two linear functions, this class lets the user write LinearFunction1 <= LinearFunction2 to define the corresponding constraint, which can potentially involve several layers of such inequalities ((A <= B <= C), or even equalities like A == B.
This class has no reason to be instanciated by the user, and is meant to be used by instances of MixedIntegerLinearProgram.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: b[2]+2*b[3] <= b[8]-5
x_0 +2 x_1 <= -5 +x_2
An elementary algebra to represent symbolic linear functions.
Returns the dictionary corresponding to the Linear Function.
A linear function is represented as a dictionary. The value are the coefficient of the variable represented by the keys ( which are integers ). The key -1 corresponds to the constant term.
EXAMPLE:
sage: from sage.numerical.mip import LinearFunction
sage: lf = LinearFunction({0 : 1, 3 : -8})
sage: lf.dict()
{0: 1, 3: -8}
Bases: exceptions.Exception
Exception raised when the solver fails.
Bases: object
MIPVariable is a variable used by the class MixedIntegerLinearProgram.
Returns the current variable’s depth.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable()
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()
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()
sage: p.set_objective(v[0] + v[1])
sage: v.keys()
[0, 1]
Returns the symbolic variables associated to the current dictionary.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable()
sage: p.set_objective(v[0] + v[1])
sage: v.values()
[x_0, x_1]
Bases: object
The MixedIntegerLinearProgram class is the link between Sage, linear programming (LP) and mixed integer programming (MIP) solvers.
See the Wikipedia article on linear programming for further information.
A mixed integer program consists of variables, linear constraints on these variables, and an objective function which is to be maximised or minimised under these constraints. An instance of MixedIntegerLinearProgram also requires the information on the direction of the optimization.
INPUT:
solver – 3 solvers should be available through this class:
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. An interface to CPLEX is not yet implemented.
solver should then be equal to one of "GLPK", "Coin", "CPLEX", or None.
If solver=None (default), the default solver is used (see default_mip_solver method.
maximization
constraint_generation – whether to require the returned solver to support constraint generation (excludes Coin). False by default.
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()
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
Adds a constraint to self.
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.
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()
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 self.
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()
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()
sage: b = p.new_variable()
sage: p.add_constraint( b[8] - b[15] <= 3*b[8] + 9)
sage: p.show()
Maximization:
<BLANKLINE>
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()
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
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()
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()
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:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: y = p.new_variable(dim=2)
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 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()
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()
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. Variables are real by default.
INPUT:
OUTPUT:
True if the variable is real; False otherwise.
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable()
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
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()
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().
Any of its fields exists, and is uniquely defined.
INPUT:
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)
sage: y = p.new_variable(dim=2, integer=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
Sets a variable or a MIPVariable as binary.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
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 real while keeping the others as they are:
sage: p.set_real(x[3])
Sets a variable or a MIPVariable as integer.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
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 real while keeping the others as they are:
sage: p.set_real(x[3])
Sets the maximum value of a variable.
INPUT
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable()
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
Sets the minimum value of a variable.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: v = p.new_variable()
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])
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()
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()
0.0
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()
With the following instruction, all the variables from x will be real (they are by default, though):
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()
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()
sage: x = p.new_variable()
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)
Solves the MixedIntegerLinearProgram.
INPUT:
OUTPUT:
The optimal value taken by the objective function.
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()
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()
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
Write the linear program as a LP file.
This function export the problem as a LP file.
INPUT:
EXAMPLE:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: p.set_objective(x[1] + x[2])
sage: p.add_constraint(-3*x[1] + 2*x[2], max=2)
sage: p.write_lp(SAGE_TMP+"/lp_problem.lp")
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()
sage: x = p.new_variable()
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(SAGE_TMP+"/lp_problem.mps")
For information about the MPS file format : http://en.wikipedia.org/wiki/MPS_%28format%29
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()
The following command:
sage: from sage.numerical.mip import Sum
sage: s = Sum([v[i] for i in xrange(90)])
is much more efficient than:
sage: s = sum([v[i] for i in xrange(90)])