CoCalc -- linearprogramming.sagews

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

Path: ForLangville/linearprogramming.sagews

Views: ⁷⁴


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

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)

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

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

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

Example 1

Example 2

Example 3

Example 5

Documentation on MixedIntegerLinearProgram

Product

Resources

Company

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more, all in one place. Commercial Alternative to JupyterHub.

Example 1

Example 2

Example 3

Example 5

Documentation on MixedIntegerLinearProgram

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.