Mixed integer linear programming

class sage.numerical.mip.LinearConstraint

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:

  • c – A LinearFunction

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
class sage.numerical.mip.LinearFunction

An elementary algebra to represent symbolic linear functions.

dict()

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}
exception sage.numerical.mip.MIPSolverException

Bases: exceptions.Exception

Exception raised when the solver fails.

class sage.numerical.mip.MIPVariable

MIPVariable is a variable used by the class MixedIntegerLinearProgram.

depth()

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

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

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

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]
class sage.numerical.mip.MixedIntegerLinearProgram

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.

A MixedIntegerLinearProgram (or LP) is defined as a maximization if maximization=True and is a minimization if maximization=False.

INPUT:

  • maximization
    • When set to True (default), the MixedIntegerLinearProgram is defined as a maximization.
    • When set to False, the MixedIntegerLinearProgram is defined as a minimization.

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)     # optional - requires Glpk or COIN-OR/CBC
4.0
add_constraint(linear_function, max=None, min=None, name=None)

Adds a constraint to self.

INPUT:

  • linear_function – Two different types of arguments are possible:
    • A linear function. In this case, arguments min or max have to be specified.
    • A linear constraint of the form A <= B, A >= B, A <= B <= C, A >= B >= C or A == B. In this case, arguments min and max will be ignored.
  • 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: p.solve()     # optional - requires Glpk or COIN-OR/CBC
6.6666666666666661

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: p.solve()     # optional - requires Glpk or COIN-OR/CBC
6.6666666666666661

TESTS:

sage: p=MixedIntegerLinearProgram()
sage: p.add_constraint(sum([]),min=2)
constraints()

Returns the list of constraints.

This function returns the constraints as a list of tuples (linear_function,min_bound,max_bound), representing the constraint:

\text{min\_bound} 
\leq 
\text{linear\_function}
\leq 
\text{max\_bound}

Variables min_bound (respectively max_bound) is set to None when the function has no lower ( respectively upper ) bound.

EXAMPLE:

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(15/10*x[1]+3*x[2], max=4)
sage: p.constraints()
[(x_0 +1/5 x_1, None, 4), (3/2 x_0 +3 x_1, None, 4)]
get_max(v)

Returns the maximum value of a variable.

INPUT:

  • v – a variable (not a MIPVariable, but one of its elements).

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

Returns the minimum value of a variable.

INPUT:

  • v – a variable (not a MIPVariable, but one of its elements).

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
get_values(*lists)

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

INPUT:

  • Any instance of MIPVariable (or one of its elements), or lists of them.

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.

EXAMPLE:

sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: y = p.new_variable(dim=2)
sage: p.set_objective(x[3] + y[2][9] + x[5])
sage: p.add_constraint(x[3] + y[2][9] + 2*x[5], max=2)
sage: p.solve() # optional - requires Glpk or COIN-OR/CBC
2.0

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

sage: p.get_values(y[2][9]) # optional - requires Glpk or COIN-OR/CBC
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])
is_binary(e)

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

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

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

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

Tests whether the variable is real. Variables are real by default.

INPUT:

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

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
new_variable(vtype=-1, dim=1, name=None)

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:

  • dim (integer) – Defines the dimension of the dictionary. If x has dimension 2, its fields will be of the form x[key1][key2].
  • vtype (integer) – Defines the type of the variables (default is REAL).
  • name (string) – A name for the variable ( default is V+number )

EXAMPLE:

sage: p = MixedIntegerLinearProgram()

The available types are p.__REAL, p.__INTEGER and p.__BINARY:

sage: x = p.new_variable(vtype=p.__REAL)
sage: y = p.new_variable(dim=2)
sage: p.add_constraint(x[2] + y[3][5], max=2)
set_binary(e)

Sets a variable or a MIPVariable as binary.

INPUT:

  • e – An instance of MIPVariable or one of its elements.

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])
set_integer(e)

Sets a variable or a MIPVariable as integer.

INPUT:

  • e – An instance of MIPVariable or one of its elements.

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])
set_max(v, max)

Sets the maximum value of a variable.

INPUT

  • v – a variable (not a MIPVariable, but one of its elements).
  • max – the maximum value the variable can take. When max=None, 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
set_min(v, min)

Sets the minimum value of a variable.

INPUT:

  • v – a variable (not a MIPVariable, but one of its elements).
  • min – the minimum value the variable can take. When min=None, 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
set_objective(obj)

Sets the objective of the MixedIntegerLinearProgram.

INPUT:

  • obj – A linear function to be optimized. ( can also be set to None or 0 when just looking for a feasible solution )

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: p.solve()     # optional - requires Glpk or COIN-OR/CBC
6.6666666666666661            
sage: p.set_objective(None)
sage: p.solve() #optional - requires Glpk or COIN-OR/CBC
0.0
set_objective_name(name)

Sets the name of the objective function.

INPUT:

  • name – A string representing the name of the objective function.

EXAMPLE:

sage: p=MixedIntegerLinearProgram()
sage: p.set_objective_name("Objective function")
set_problem_name(name)

Sets the name of the MixedIntegerLinearProgram.

INPUT:

  • name – A string representing the name of the MixedIntegerLinearProgram.

EXAMPLE:

sage: p=MixedIntegerLinearProgram()
sage: p.set_problem_name("Test program")
sage: p
Mixed Integer Program "Test program" ( maximization, 0 variables, 0 constraints )
set_real(e)

Sets a variable or a MIPVariable as real.

INPUT:

  • e – An instance of MIPVariable or one of its elements.

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

Displays the MixedIntegerLinearProgram in a human-readable way.

EXAMPLES:

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="Constraint_1")
sage: p.show()
Maximization:
  x_0 +x_1
Constraints:
  Constraint_1: -3 x_0 +2 x_1 <= 2
Variables:
  x_0 is a real variable (min=0.0, max=+oo)
  x_1 is a real variable (min=0.0, max=+oo)
solve(solver=None, log=False, objective_only=False)

Solves the MixedIntegerLinearProgram.

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 (COIN if available, GLPK otherwise).

  • log – This boolean variable indicates whether progress should be printed during the computations.

  • objective_only – Boolean variable.

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

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: p.solve()           # optional - requires Glpk or COIN-OR/CBC
   6.6666666666666661
   sage: p.get_values(x)     # optional random - requires Glpk or COIN-OR/CBC
   {0: 0.0, 1: 1.3333333333333333}

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)     # optional - requires Glpk or COIN-OR/CBC
   4.0

TESTS:

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: p.set_binary(b)
sage: p.solve(solver='GLPK', objective_only=True) # optional - requires GLPK
... 
RuntimeError
write_lp(filename)

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.

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") # optional - requires GLPK

For more information about the LP file format : http://lpsolve.sourceforge.net/5.5/lp-format.htm

write_mps(filename, modern=True)

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") # optional - requires GLPK

For information about the MPS file format : http://en.wikipedia.org/wiki/MPS_%28format%29

Previous topic

Knapsack Problems

Next topic

Numerical Root Finding and Optimization

This Page