Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 65

Example 1

p = MixedIntegerLinearProgram(maximization=false) p
Mixed Integer Program ( minimization, 0 variables, 0 constraints )
x=p.new_variable(real=True,nonnegative=True) C=x[0] T=x[1]
p.set_objective(12*C-13*T)
p.add_constraint(6*C+7*T<=21)
p.solve()
-39.0
p.get_values(C)
0.0
p.get_values(T)
3.0
p.polyhedron().show()

Example 2

p = MixedIntegerLinearProgram()
x=p.new_variable(nonnegative=True)
p.set_objective(x[0] + x[1] + 3*x[2])
p.add_constraint(x[0] + 2*x[1] <= 4) p.add_constraint(5*x[2] - x[1] <= 8)
p.solve()
8.8
p.get_values(x)
{0: 4.000000000000001, 1: 0.0, 2: 1.6}
p.show()
Maximization: x_0 + x_1 + 3.0 x_2 Constraints: x_0 + 2.0 x_1 <= 4.0 - x_1 + 5.0 x_2 <= 8.0 Variables: x_0 is a continuous variable (min=0.0, max=+oo) x_1 is a continuous variable (min=0.0, max=+oo) x_2 is a continuous variable (min=0.0, max=+oo)

Example 3

p=MixedIntegerLinearProgram()
x=p.new_variable(nonnegative=True)
p.add_constraint(-3*x[0]+x[1]<=2) p.add_constraint(x[1]<=11) p.add_constraint(x[0]-x[1]<=3) p.add_constraint(x[0]<=6)
p.set_objective(x[0]+2*x[1])
p.solve()
28.0
p.show()
Maximization: x_0 + 2.0 x_1 Constraints: -3.0 x_0 + x_1 <= 2.0 x_1 <= 11.0 x_0 - x_1 <= 3.0 x_0 <= 6.0 Variables: x_0 is a continuous variable (min=0.0, max=+oo) x_1 is a continuous variable (min=0.0, max=+oo)
p.get_values(x)
{0: 6.0, 1: 11.0}
p.polyhedron().show()

Example 4:

Generate an n×nn \times n magic square.

p=MixedIntegerLinearProgram(solver="GLPK")
x=p.new_variable(binary=True)
n=4 tot=34
range(1,n^2+1)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
# each row must add up to 15 for i in range(0,n): p.add_constraint(add([k*x[i,j,k] for j in range(0,n) for k in range(1,n^2+1)]) == tot)
# each column must add up to 15 for j in range(0,n): p.add_constraint(add([k*x[i,j,k] for i in range(0,n) for k in range(1,n^2+1)]) == tot)
# diagonals must add up to 15 p.add_constraint(add([k*x[i,i,k] for i in range(0,n) for k in range(1,n^2+1)]) == tot) p.add_constraint(add([k*x[n-1-i,i,k] for i in range(0,n) for k in range(1,n^2+1)]) == tot)
# each integer must be used just once for k in range(1,n^2+1): p.add_constraint(add([x[i,j,k] for i in range(0,n) for j in range(0,n)])==1)
# each position contains only one integer for i in range(0,n): for j in range(0,n): p.add_constraint(add([x[i,j,k] for k in range(1,n^2+1)]) ==1 )
p
Mixed Integer Program ( maximization, 256 variables, 42 constraints )
p.solve()
0.0
ans=p.get_values(x) ans
{(1, 2, 8): 1.0, (1, 3, 16): 0.0, (1, 1, 7): 0.0, (3, 1, 10): 0.0, (3, 0, 3): 0.0, (0, 3, 12): 0.0, (0, 0, 8): 0.0, (0, 2, 15): 0.0, (1, 2, 10): 0.0, (3, 1, 8): 0.0, (3, 0, 5): 0.0, (0, 0, 9): 0.0, (0, 2, 1): 0.0, (1, 3, 12): 1.0, (1, 2, 12): 0.0, (0, 2, 12): 0.0, (0, 0, 5): 0.0, (3, 0, 7): 1.0, (0, 2, 3): 1.0, (1, 2, 14): 0.0, (3, 1, 4): 0.0, (3, 0, 9): 0.0, (3, 2, 2): 0.0, (0, 3, 13): 0.0, (2, 3, 8): 0.0, (0, 2, 5): 0.0, (0, 3, 16): 0.0, (3, 1, 2): 0.0, (3, 0, 11): 0.0, (0, 1, 8): 0.0, (0, 0, 16): 0.0, (0, 2, 7): 0.0, (1, 2, 2): 0.0, (1, 0, 11): 0.0, (0, 0, 4): 0.0, (3, 0, 13): 0.0, (3, 2, 6): 0.0, (0, 1, 10): 0.0, (2, 1, 16): 0.0, (1, 2, 4): 0.0, (1, 0, 9): 0.0, (3, 0, 15): 0.0, (3, 2, 4): 0.0, (0, 3, 2): 0.0, (0, 1, 12): 0.0, (2, 2, 16): 0.0, (1, 3, 7): 0.0, (1, 2, 6): 0.0, (1, 0, 15): 0.0, (3, 2, 10): 0.0, (0, 1, 14): 0.0, (1, 3, 5): 0.0, (1, 0, 13): 0.0, (2, 2, 7): 0.0, (0, 0, 3): 0.0, (3, 2, 8): 0.0, (2, 3, 4): 0.0, (1, 3, 3): 0.0, (1, 0, 3): 0.0, (3, 0, 16): 0.0, (0, 0, 14): 0.0, (3, 2, 14): 1.0, (0, 3, 3): 0.0, (0, 1, 2): 0.0, (0, 3, 11): 0.0, (1, 3, 1): 0.0, (1, 0, 1): 1.0, (3, 3, 1): 0.0, (3, 2, 12): 0.0, (0, 1, 4): 0.0, (0, 3, 9): 0.0, (1, 3, 15): 0.0, (1, 0, 7): 0.0, (0, 1, 9): 0.0, (0, 0, 2): 0.0, (3, 3, 3): 0.0, (0, 0, 7): 0.0, (0, 1, 6): 1.0, (0, 3, 15): 1.0, (1, 3, 13): 0.0, (1, 1, 8): 0.0, (1, 2, 16): 0.0, (1, 0, 5): 0.0, (3, 3, 5): 0.0, (2, 2, 9): 1.0, (0, 3, 8): 0.0, (2, 1, 9): 0.0, (1, 3, 11): 0.0, (1, 1, 10): 0.0, (0, 3, 6): 0.0, (3, 1, 16): 0.0, (3, 3, 7): 0.0, (2, 2, 1): 0.0, (2, 2, 15): 0.0, (2, 1, 7): 0.0, (1, 3, 9): 0.0, (1, 1, 12): 0.0, (3, 1, 6): 0.0, (0, 0, 1): 0.0, (3, 3, 9): 0.0, (1, 3, 4): 0.0, (2, 2, 13): 0.0, (0, 3, 1): 0.0, (1, 1, 14): 0.0, (3, 3, 11): 0.0, (0, 0, 15): 0.0, (2, 1, 5): 0.0, (2, 1, 3): 0.0, (3, 1, 15): 0.0, (0, 0, 10): 1.0, (3, 3, 13): 0.0, (0, 0, 13): 0.0, (2, 0, 12): 0.0, (0, 1, 16): 0.0, (0, 3, 5): 0.0, (1, 1, 2): 0.0, (3, 1, 13): 0.0, (2, 0, 7): 0.0, (3, 3, 15): 0.0, (0, 0, 11): 0.0, (0, 2, 10): 0.0, (0, 2, 14): 0.0, (1, 1, 4): 0.0, (3, 1, 11): 1.0, (3, 0, 2): 0.0, (2, 0, 5): 0.0, (2, 2, 5): 0.0, (2, 0, 8): 0.0, (2, 3, 16): 0.0, (0, 1, 13): 0.0, (1, 2, 9): 0.0, (1, 1, 6): 0.0, (3, 1, 9): 0.0, (0, 3, 10): 0.0, (3, 0, 4): 0.0, (2, 3, 10): 0.0, (2, 0, 10): 0.0, (1, 2, 11): 0.0, (3, 1, 7): 0.0, (2, 0, 6): 0.0, (3, 0, 6): 0.0, (2, 2, 3): 0.0, (2, 0, 4): 0.0, (0, 1, 7): 0.0, (1, 2, 13): 0.0, (3, 1, 5): 0.0, (3, 3, 16): 0.0, (3, 0, 8): 0.0, (0, 3, 7): 0.0, (2, 3, 6): 0.0, (1, 2, 15): 0.0, (3, 1, 3): 0.0, (2, 1, 15): 0.0, (3, 0, 10): 0.0, (3, 2, 3): 0.0, (2, 0, 2): 0.0, (0, 2, 4): 0.0, (1, 2, 1): 0.0, (1, 0, 10): 0.0, (3, 1, 1): 0.0, (2, 0, 1): 0.0, (3, 0, 12): 0.0, (2, 2, 2): 0.0, (2, 3, 13): 0.0, (0, 2, 6): 0.0, (0, 2, 9): 0.0, (1, 2, 3): 0.0, (1, 0, 8): 0.0, (1, 1, 16): 0.0, (3, 0, 14): 0.0, (3, 2, 7): 0.0, (2, 1, 10): 0.0, (2, 3, 15): 0.0, (0, 1, 3): 0.0, (1, 2, 5): 0.0, (1, 0, 14): 0.0, (0, 2, 2): 0.0, (3, 2, 5): 0.0, (2, 3, 9): 0.0, (1, 3, 6): 0.0, (1, 2, 7): 0.0, (1, 0, 12): 0.0, (0, 1, 1): 0.0, (3, 2, 11): 0.0, (0, 1, 15): 0.0, (0, 2, 8): 0.0, (1, 0, 2): 0.0, (3, 2, 9): 0.0, (2, 3, 5): 1.0, (2, 1, 14): 0.0, (2, 1, 1): 0.0, (1, 3, 2): 0.0, (0, 2, 13): 0.0, (2, 1, 13): 0.0, (2, 3, 12): 0.0, (2, 3, 7): 0.0, (2, 1, 12): 0.0, (0, 2, 16): 0.0, (3, 2, 1): 0.0, (1, 0, 6): 0.0, (3, 2, 15): 0.0, (2, 0, 3): 0.0, (3, 2, 13): 0.0, (2, 3, 1): 0.0, (0, 3, 14): 0.0, (1, 3, 14): 0.0, (1, 1, 9): 0.0, (1, 0, 4): 0.0, (3, 3, 2): 1.0, (0, 0, 6): 0.0, (2, 3, 3): 0.0, (2, 1, 8): 0.0, (2, 0, 16): 1.0, (0, 1, 5): 0.0, (1, 1, 11): 0.0, (3, 3, 4): 0.0, (2, 2, 8): 0.0, (2, 1, 6): 0.0, (2, 2, 10): 0.0, (1, 3, 10): 0.0, (1, 1, 13): 1.0, (2, 2, 4): 0.0, (3, 3, 6): 0.0, (2, 2, 14): 0.0, (2, 1, 4): 1.0, (1, 3, 8): 0.0, (1, 1, 15): 0.0, (2, 2, 11): 0.0, (2, 0, 11): 0.0, (3, 2, 16): 0.0, (3, 3, 8): 0.0, (0, 1, 11): 0.0, (2, 2, 12): 0.0, (2, 1, 2): 0.0, (2, 3, 2): 0.0, (1, 1, 1): 0.0, (3, 3, 10): 0.0, (2, 3, 14): 0.0, (2, 0, 13): 0.0, (0, 3, 4): 0.0, (2, 3, 11): 0.0, (1, 1, 3): 0.0, (3, 1, 14): 0.0, (3, 3, 12): 0.0, (0, 0, 12): 0.0, (2, 0, 15): 0.0, (2, 1, 11): 0.0, (0, 2, 11): 0.0, (1, 1, 5): 0.0, (3, 1, 12): 0.0, (1, 0, 16): 0.0, (3, 0, 1): 0.0, (3, 3, 14): 0.0, (2, 2, 6): 0.0, (2, 0, 9): 0.0, (2, 0, 14): 0.0}
m=matrix(n,n)
for i in range(0,n): for j in range(0,n): for k in range(1,n^2+1): if ans[(i,j,k)]>0: print (i,j,k) m[i,j]=k
(0, 0, 10) (0, 1, 6) (0, 2, 3) (0, 3, 15) (1, 0, 1) (1, 1, 13) (1, 2, 8) (1, 3, 12) (2, 0, 16) (2, 1, 4) (2, 2, 9) (2, 3, 5) (3, 0, 7) (3, 1, 11) (3, 2, 14) (3, 3, 2)
show(m)
(10631511381216495711142)\displaystyle \left(\begin{array}{rrrr} 10 & 6 & 3 & 15 \\ 1 & 13 & 8 & 12 \\ 16 & 4 & 9 & 5 \\ 7 & 11 & 14 & 2 \end{array}\right)

Example 5

Linear program with matrix and vector formulation

p=MixedIntegerLinearProgram() x=p.new_variable(nonnegative=True)
A=matrix([[1,2],[4,2],[-1,1]]) c=vector([4,12,1])
p.add_constraint(A*x<=c)
p.set_objective(x[0]+x[1])
p
Mixed Integer Program ( maximization, 2 variables, 3 constraints )
p.show()
Maximization: x_0 + x_1 Constraints: x_0 + 2.0 x_1 <= 4.0 4.0 x_0 + 2.0 x_1 <= 12.0 - 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)
p.solve()
3.333333333333333
p.get_values(x)
{0: 2.6666666666666665, 1: 0.6666666666666667}
p.polyhedron().show()
# another way to plot to show the contours var('x0 x1') rp=region_plot([x0+2*x1<=4,4*x0+2*x1<=12,-x0+x1<=1],(x0,0,3),(x1,0,2),incol='red') rp+=contour_plot(x0+x1,(x0,0,3),(x1,0,2),fill=false,labels=true,contours=[0,1,2,3,4]) rp
(x0, x1)

Documentation on MixedIntegerLinearProgram

MixedIntegerLinearProgram?
File: /usr/local/sage/sage-6.5/src/sage/numerical/mip.pyx Signature : MixedIntegerLinearProgram() Docstring : 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 http://en.wikipedia.org/wiki/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. * Gurobi ("solver="Gurobi""). See the Gurobi web site. * CVXOPT ("solver="CVXOPT""). See the CVXOPT web site. * PPL ("solver="PPL""). See the PPL web site. * If "solver=None" (default), the default solver is used (see "default_mip_solver()") * "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". Warning: All LP variables are non-negative by default (see "new_variable()" and "set_min()"). See also: * "default_mip_solver()" -- Returns/Sets the default MIP solver. 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 http://trac.sagemath.org/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