Integer Programming¶
There are three types of model problems:
Total integer model: all the decision variables are required to have integer solution values
Binary integer (0-1) model: all decision variables must have zero or one integer value
Mixed-integer (MI) model: some decision variables required to have integer values
A 0 - 1 Integer Model:¶
Solve the following LP problem:
\[\begin{split}
\begin{align}
&\text{max}\\
&\qquad z=300x_1+90x_2+400x_3+150x_4\\
&\text{s.t.}\\
&\qquad 35000x_1+10000x_2+25000x_3+90000x_4\le120000\\
&\qquad 4x_1+2x_2+7x_3+3x_4\le 12\\
&\qquad x_1+x_2 \le 1\\
&\qquad x_1,x_2,x_3,x_4 = 0~\text{or}~1\\
\end{align}
\end{split}\]
Note to make use of vtype = GRB.BINARY
!pip install gurobipy
Requirement already satisfied: gurobipy in /usr/local/lib/python3.7/dist-packages (9.5.0)
from gurobipy import *
import numpy as np
c = [300,90,400,150]
A = [[35000,10000,25000,90000 ],
[4,2,7,3 ],
[1,1,0,0 ]]
b = [120000,12,1]
print(np.array(c).shape,np.array(A).shape,np.array(b).shape)
decision_variables = range(len(c))
constraints = range(np.array(A).shape[0])
m = Model("Example")
x = []
for i in decision_variables:
x.append(m.addVar(lb = 0, vtype = GRB.BINARY, name = 'x' + str(i)))
# list comprehensions
m.setObjective(quicksum(c[i] * x[i] for i in decision_variables) , GRB.MAXIMIZE)
m.addConstrs((quicksum(A[j][i] * x[i] for i in decision_variables)
<= b[j] for j in constraints), "constraints")
m.optimize()
for var in m.getVars(): # descision variable
print(var.varName, '=', var.x, var.obj)
print("objective value =", m.objVal)
(4,) (3, 4) (3,)
Restricted license - for non-production use only - expires 2023-10-25
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 3 rows, 4 columns and 10 nonzeros
Model fingerprint: 0x593445fa
Variable types: 0 continuous, 4 integer (4 binary)
Coefficient statistics:
Matrix range [1e+00, 9e+04]
Objective range [9e+01, 4e+02]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+05]
Found heuristic solution: objective 700.0000000
Presolve removed 3 rows and 4 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 1: 700
Optimal solution found (tolerance 1.00e-04)
Best objective 7.000000000000e+02, best bound 7.000000000000e+02, gap 0.0000%
x0 = 1.0 300.0
x1 = 0.0 90.0
x2 = 1.0 400.0
x3 = 0.0 150.0
objective value = 700.0
A Total Integer Model:¶
Solve the following LP problem:
\[\begin{split}
\begin{align}
&\text{max}\\
&\qquad z=100x_1+150x_2\\
&\text{s.t.}\\
&\qquad 8000x_1+4000x_2\le 40000\\
&\qquad 15x_1+30x_2\le200\\
&\qquad x_1,x_2\ge \text{and integer}\\
\end{align}
\end{split}\]
Note to make use of vtype = GRB.INTEGER
c = [100,150]
A = [[8000,4000],
[15,30 ]]
b = [40000,200]
print(np.array(c).shape,np.array(A).shape,np.array(b).shape)
decision_variables = range(len(c))
constraints = range(np.array(A).shape[0])
m = Model("Example")
x = []
for i in decision_variables:
x.append(m.addVar(lb = 0, vtype = GRB.INTEGER, name = 'x' + str(i)))
m.setObjective(quicksum(c[i] * x[i] for i in decision_variables) , GRB.MAXIMIZE)
m.addConstrs((quicksum(A[j][i] * x[i] for i in decision_variables)
<= b[j] for j in constraints), "constraints")
m.optimize()
for var in m.getVars(): # descision variable
print(var.varName, '=', var.x, var.obj)
print("objective value =", m.objVal)
(2,) (2, 2) (2,)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x8c581e3f
Variable types: 0 continuous, 2 integer (0 binary)
Coefficient statistics:
Matrix range [2e+01, 8e+03]
Objective range [1e+02, 2e+02]
Bounds range [0e+00, 0e+00]
RHS range [2e+02, 4e+04]
Found heuristic solution: objective 500.0000000
Presolve time: 0.00s
Presolved: 2 rows, 2 columns, 4 nonzeros
Variable types: 0 continuous, 2 integer (0 binary)
Found heuristic solution: objective 550.0000000
Root relaxation: objective 1.033333e+03, 2 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1033.33333 0 2 550.00000 1033.33333 87.9% - 0s
H 0 0 1000.0000000 1033.33333 3.33% - 0s
0 0 1033.33333 0 2 1000.00000 1033.33333 3.33% - 0s
Explored 1 nodes (2 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 2 (of 2 available processors)
Solution count 3: 1000 550 500
Optimal solution found (tolerance 1.00e-04)
Best objective 1.000000000000e+03, best bound 1.000000000000e+03, gap 0.0000%
x0 = 1.0 100.0
x1 = 6.0 150.0
objective value = 1000.0
Mixed Integer Model¶
Solve the following LP problem:
\[\begin{split}
\begin{align}
&\text{max}\\
&\qquad z=9000x_1+1500x_2+1000x_3\\
&\text{s.t.}\\
&\qquad 50000x_1+12000x_2+8000x_3\le25000\\
&\qquad x_1\le 4\\
&\qquad x_2\le 15\\
&\qquad x_3\le 20\\
&\qquad x_2\ge 0\\
&\qquad x_1,x_3\ge \text{and integer}\\
\end{align}
\end{split}\]
Note that vtype has a mixture of INTEGER and CONTINUOUS
c = [9000,1500,1000]
A = [[50000,12000,8000],
[1,0,0,0 ],
[0,1,0,0 ],
[0,0,1,0 ],
[0,-1,0,0 ]]
b = [250000,4,15,20,0]
print(np.array(c).shape,np.array(A).shape,np.array(b).shape)
decision_variables = range(len(c))
constraints = range(np.array(A).shape[0])
m = Model("Example")
x = []
x.append(m.addVar(lb = 0, vtype = GRB.INTEGER, name = 'x' + str(i)))
x.append(m.addVar(lb = 0, vtype = GRB.CONTINUOUS, name = 'x' + str(i)))
x.append(m.addVar(lb = 0, vtype = GRB.INTEGER, name = 'x' + str(i)))
m.setObjective(quicksum(c[i] * x[i] for i in decision_variables) , GRB.MAXIMIZE)
m.addConstrs((quicksum(A[j][i] * x[i] for i in decision_variables)
<= b[j] for j in constraints), "constraints")
m.optimize()
for var in m.getVars(): # descision variable
print(var.varName, '=', var.x, var.obj)
print("objective value =", m.objVal)
(3,) (5,) (5,)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 5 rows, 3 columns and 7 nonzeros
Model fingerprint: 0x3b8b5be3
Variable types: 1 continuous, 2 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 5e+04]
Objective range [1e+03, 9e+03]
Bounds range [0e+00, 0e+00]
RHS range [4e+00, 2e+05]
Found heuristic solution: objective 42250.000000
Presolve removed 4 rows and 0 columns
Presolve time: 0.00s
Presolved: 1 rows, 3 columns, 3 nonzeros
Variable types: 0 continuous, 3 integer (0 binary)
Root relaxation: cutoff, 0 iterations, 0.00 seconds (0.00 work units)
Explored 1 nodes (0 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 2 (of 2 available processors)
Solution count 1: 42250
Optimal solution found (tolerance 1.00e-04)
Best objective 4.225000000000e+04, best bound 4.225000000000e+04, gap 0.0000%
x1 = 4.0 9000.0
x1 = 4.166666666666667 1500.0
x1 = -0.0 1000.0
objective value = 42250.0
/usr/local/lib/python3.7/dist-packages/ipykernel_launcher.py:8: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray
/usr/local/lib/python3.7/dist-packages/ipykernel_launcher.py:10: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray
# Remove the CWD from sys.path while we load stuff.
Problem Example: C5Q5¶
Solve the following LP problem:
\[\begin{split}
\begin{align}
&\text{max}\\
&\qquad z=50x_1+40x_2\\
&\text{s.t.}\\
&\qquad 3x_1+5x_2\le 150\\
&\qquad 10x_1+4x_2\le 200\\
&\qquad x_1,x_2\ge \text{and integer}\\
\end{align}
\end{split}\]
c = [50,40]
A = [[3,5 ],
[10,4 ]]
b = [150,200]
print(np.array(c).shape,np.array(A).shape,np.array(b).shape)
decision_variables = range(len(c))
constraints = range(np.array(A).shape[0])
m = Model("C5Q5")
x = []
for i in decision_variables:
x.append(m.addVar(lb = 0, vtype = GRB.CONTINUOUS, name = 'x' + str(i)))
m.setObjective(quicksum(c[i] * x[i] for i in decision_variables) , GRB.MAXIMIZE)
m.addConstrs((quicksum(A[j][i] * x[i] for i in decision_variables)
<= b[j] for j in constraints), "constraints")
m.optimize()
for var in m.getVars(): # descision variable
print(var.varName, '=', var.x, (var.obj,var.SAObjLow, var.SAObjUp, var.RC))
for con in m.getConstrs(): # constraints
print(con.ConstrName, ': slack =', con.slack,', shadow price=',
con.pi,',', (con.RHS, con.SARHSLow, con.SARHSUp))
print("objective value =", m.objVal)
(2,) (2, 2) (2,)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0xc186269e
Coefficient statistics:
Matrix range [3e+00, 1e+01]
Objective range [4e+01, 5e+01]
Bounds range [0e+00, 0e+00]
RHS range [2e+02, 2e+02]
Presolve time: 0.01s
Presolved: 2 rows, 2 columns, 4 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 9.0000000e+31 2.750000e+30 9.000000e+01 0s
2 1.4736842e+03 0.000000e+00 0.000000e+00 0s
Solved in 2 iterations and 0.02 seconds (0.00 work units)
Optimal objective 1.473684211e+03
x0 = 10.526315789473683 (50.0, 24.000000000000004, 100.0, 0.0)
x1 = 23.68421052631579 (40.0, 19.999999999999996, 83.33333333333334, 0.0)
constraints[0] : slack = 0.0 , shadow price= 5.2631578947368425 , (150.0, 59.999999999999986, 250.0)
constraints[1] : slack = 0.0 , shadow price= 3.4210526315789473 , (200.0, 120.00000000000001, 500.00000000000006)
objective value = 1473.6842105263158
y=[]
for var in m.getVars():
y.append(np.floor(var.x))
np.array(y).dot(np.array((50,40)))
1420.0
c = [50,40]
A = [[3,5 ],
[10,4 ]]
b = [150,200]
print(np.array(c).shape,np.array(A).shape,np.array(b).shape)
decision_variables = range(len(c))
constraints = range(np.array(A).shape[0])
m = Model("C5Q5")
x = []
for i in decision_variables:
x.append(m.addVar(lb = 0, vtype = GRB.INTEGER, name = 'x' + str(i)))
m.setObjective(quicksum(c[i] * x[i] for i in decision_variables) , GRB.MAXIMIZE)
m.addConstrs((quicksum(A[j][i] * x[i] for i in decision_variables)
<= b[j] for j in constraints), "constraints")
m.optimize()
for var in m.getVars(): # descision variable
print(var.varName, '=', var.x, var.obj)
#for con in m.getConstrs(): # constraints
# print(con.ConstrName, ': slack =', con.slack,', shadow price=',
# con.pi,',', (con.RHS, con.SARHSLow, con.SARHSUp))
print("objective value =", m.objVal)
(2,) (2, 2) (2,)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0xc188e0de
Variable types: 0 continuous, 2 integer (0 binary)
Coefficient statistics:
Matrix range [3e+00, 1e+01]
Objective range [4e+01, 5e+01]
Bounds range [0e+00, 0e+00]
RHS range [2e+02, 2e+02]
Found heuristic solution: objective 1000.0000000
Presolve time: 0.00s
Presolved: 2 rows, 2 columns, 4 nonzeros
Variable types: 0 continuous, 2 integer (0 binary)
Root relaxation: objective 1.473684e+03, 2 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1473.68421 0 2 1000.00000 1473.68421 47.4% - 0s
H 0 0 1460.0000000 1473.68421 0.94% - 0s
0 0 1473.68421 0 2 1460.00000 1473.68421 0.94% - 0s
Explored 1 nodes (2 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 2 (of 2 available processors)
Solution count 2: 1460 1000
Optimal solution found (tolerance 1.00e-04)
Best objective 1.460000000000e+03, best bound 1.460000000000e+03, gap 0.0000%
x0 = 10.0 50.0
x1 = 24.0 40.0
objective value = 1460.0
Problem Example: C5Q13¶
Solve the following LP problem:
\[\begin{split}
\begin{align}
&\text{max}\\
&\qquad z=85000 x_1 + 60000 x_2 – 18000 y_1\\
&\text{s.t.}\\
&\qquad x_1+x_2\le 10\\
&\qquad 10000x_1+7000x_2\le 72000\\
&\qquad x_1-10y_1\le 0\\
&\qquad x_1,x_2\ge \text{and integer}\\
&\qquad y_1= 0~\text{or}~1\\
\end{align}
\end{split}\]
c = [85000,60000,-18000]
A = [[1,1,0 ],
[10000,7000,0 ],
[1,0,-10],
[-1,0,10]]
b = [10,72000,0,9]
print(np.array(c).shape,np.array(A).shape,np.array(b).shape)
decision_variables = range(len(c))
constraints = range(np.array(A).shape[0])
m = Model("C5Q13")
x = []
x.append(m.addVar(lb = 0, vtype = GRB.INTEGER, name = 'x1'))
x.append(m.addVar(lb = 0, vtype = GRB.INTEGER, name = 'x2'))
x.append(m.addVar(lb = 0, vtype = GRB.BINARY, name = 'x3'))
m.setObjective(quicksum(c[i] * x[i] for i in decision_variables) , GRB.MAXIMIZE)
m.addConstrs((quicksum(A[j][i] * x[i] for i in decision_variables)
<= b[j] for j in constraints), "constraints")
m.optimize()
for var in m.getVars(): # descision variable
print(var.varName, '=', var.x, var.obj)
#for con in m.getConstrs(): # constraints
# print(con.ConstrName, ': slack =', con.slack,', shadow price=',
# con.pi,',', (con.RHS, con.SARHSLow, con.SARHSUp))
print("objective value =", m.objVal)
(3,) (4, 3) (4,)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 4 rows, 3 columns and 8 nonzeros
Model fingerprint: 0x11909cb7
Variable types: 0 continuous, 3 integer (1 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+04]
Objective range [2e+04, 8e+04]
Bounds range [1e+00, 1e+00]
RHS range [9e+00, 7e+04]
Found heuristic solution: objective 600000.00000
Presolve time: 0.00s
Presolved: 4 rows, 3 columns, 8 nonzeros
Variable types: 0 continuous, 3 integer (1 binary)
Root relaxation: cutoff, 1 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 cutoff 0 600000.000 600000.000 0.00% - 0s
Explored 1 nodes (1 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 2 (of 2 available processors)
Solution count 1: 600000
Optimal solution found (tolerance 1.00e-04)
Best objective 6.000000000000e+05, best bound 6.000000000000e+05, gap 0.0000%
x1 = -0.0 85000.0
x2 = 10.0 60000.0
x3 = -0.0 -18000.0
objective value = 600000.0
Problem Example: C5Q14¶
Solve the following LP problem:
\[\begin{split}
\begin{align}
&\text{max}\\
&\qquad z=.36x_1 + .82x_2 + .29x_3 + .16x_4
+ .56x_5 + .61x_6 + .48x_7 + .41x_8\\
&\text{s.t.}\\
&\qquad 60x_1 + 110x_2 + 53x_3 + 47x_4 +
92x_5 +85x_6 +73x_7 +65x_8\le 300\\
&\qquad 7x_1 + 9x_2 + 8x_3 + 4x_4 + 7x_5 +
6x_6 +8x_7 +5x_8\le 40\\
&\qquad x_2-x_5\le 0\\
&\qquad x_i= 0~\text{or}~1\\
\end{align}
\end{split}\]
c = [.36,.82,.29,.16,.56,.61,.48,.41]
A = [[60,110,53,47,92,85,73,65 ],
[7,9,8,4,7,6,8,5 ],
[0,1,0,0,-1,0,0,0]]
b = [300,40,0]
print(np.array(c).shape,np.array(A).shape,np.array(b).shape)
decision_variables = range(len(c))
constraints = range(np.array(A).shape[0])
m = Model("C5Q14")
x = []
for i in decision_variables:
x.append(m.addVar(lb = 0, vtype = GRB.BINARY, name = 'x' + str(i)))
m.setObjective(quicksum(c[i] * x[i] for i in decision_variables) , GRB.MAXIMIZE)
m.addConstrs((quicksum(A[j][i] * x[i] for i in decision_variables)
<= b[j] for j in constraints), "constraints")
m.optimize()
for var in m.getVars(): # descision variable
print(var.varName, '=', var.x, var.obj)
#for con in m.getConstrs(): # constraints
# print(con.ConstrName, ': slack =', con.slack,', shadow price=',
# con.pi,',', (con.RHS, con.SARHSLow, con.SARHSUp))
print("objective value =", m.objVal*1e6)
(8,) (3, 8) (3,)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 3 rows, 8 columns and 18 nonzeros
Model fingerprint: 0xd75ca42c
Variable types: 0 continuous, 8 integer (8 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+02]
Objective range [2e-01, 8e-01]
Bounds range [1e+00, 1e+00]
RHS range [4e+01, 3e+02]
Found heuristic solution: objective 1.3700000
Presolve removed 1 rows and 0 columns
Presolve time: 0.00s
Presolved: 2 rows, 8 columns, 10 nonzeros
Variable types: 0 continuous, 8 integer (8 binary)
Found heuristic solution: objective 1.6600000
Root relaxation: objective 2.042603e+00, 3 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 2.04260 0 1 1.66000 2.04260 23.0% - 0s
H 0 0 1.9900000 2.04260 2.64% - 0s
0 0 infeasible 0 1.99000 1.99000 0.00% - 0s
Cutting planes:
GUB cover: 1
Explored 1 nodes (4 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 2 (of 2 available processors)
Solution count 3: 1.99 1.66 1.37
Optimal solution found (tolerance 1.00e-04)
Best objective 1.990000000000e+00, best bound 1.990000000000e+00, gap 0.0000%
x0 = -0.0 0.36
x1 = 1.0 0.82
x2 = -0.0 0.29
x3 = -0.0 0.16
x4 = 1.0 0.56
x5 = 1.0 0.61
x6 = 0.0 0.48
x7 = -0.0 0.41
objective value = 1990000.0
Problem Example: C5Q15¶
Solve the following LP problem:
\[\begin{split}
\begin{align}
&\text{max}\\
&\qquad z=x_1 +x_2 +x_3 +x_4 +x_5 +x_6\\
&\text{s.t.}\\
&\qquad x_6+x_1 \ge 90\\
&\qquad x_1+x_2 \ge 215\\
&\qquad x_2+x_3 \ge 250\\
&\qquad x_3+x_4 \ge 65\\
&\qquad x_4+x_5 \ge 300\\
&\qquad x_5+x_6 \ge 125\\
&\qquad x_i \ge 0~ \text{and integer}\\
\end{align}
\end{split}\]
c = [1,1,1,1,1,1]
A = [[1,0,0,0,0,1],
[1,1,0,0,0,0],
[0,1,1,0,0,0],
[0,0,1,1,0,0],
[0,0,0,1,1,0],
[0,0,0,0,1,1]]
b = [90,215,250,65,300,125]
print(np.array(c).shape,np.array(A).shape,np.array(b).shape)
decision_variables = range(len(c))
constraints = range(np.array(A).shape[0])
m = Model("C5Q15")
x = []
for i in decision_variables:
x.append(m.addVar(lb = 0, vtype = GRB.INTEGER, name = 'x' + str(i)))
m.setObjective(quicksum(c[i] * x[i] for i in decision_variables) , GRB.MINIMIZE)
m.addConstrs((quicksum(A[j][i] * x[i] for i in decision_variables)
>= b[j] for j in constraints), "constraints")
m.optimize()
for var in m.getVars(): # descision variable
print(var.varName, '=', var.x, var.obj)
#for con in m.getConstrs(): # constraints
# print(con.ConstrName, ': slack =', con.slack,', shadow price=',
# con.pi,',', (con.RHS, con.SARHSLow, con.SARHSUp))
print("objective value =", m.objVal)
(6,) (6, 6) (6,)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 6 rows, 6 columns and 12 nonzeros
Model fingerprint: 0xeba1cb46
Variable types: 0 continuous, 6 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [6e+01, 3e+02]
Found heuristic solution: objective 640.0000000
Presolve time: 0.00s
Presolved: 6 rows, 6 columns, 12 nonzeros
Variable types: 0 continuous, 6 integer (0 binary)
Root relaxation: cutoff, 3 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 cutoff 0 640.00000 640.00000 0.00% - 0s
Explored 1 nodes (3 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 2 (of 2 available processors)
Solution count 1: 640
Optimal solution found (tolerance 1.00e-04)
Best objective 6.400000000000e+02, best bound 6.400000000000e+02, gap 0.0000%
x0 = 0.0 1.0
x1 = 215.0 1.0
x2 = 35.0 1.0
x3 = 30.0 1.0
x4 = 270.0 1.0
x5 = 90.0 1.0
objective value = 640.0
Problem Example: C5Q17¶
Solve the following LP problem:
\[\begin{split}
\begin{align}
&\text{min}\\
&\qquad z=25000x_1 + 7000x_2 + 9000x_3\\
&\text{s.t.}\\
&\qquad 53000x_1+30000x_2+41000x_3 \ge 200,000\\
&\qquad (32000x_1 + 20000x_2 +18000x_3)/(21000x_1 +10000x_2 +23000x_3) \ge 1.5\\
&\qquad (34000x_1 +12000x_2 + 24000x_3)/(53000x_1 +30000x_2 +41000x_3) \ge .60\\
&\qquad x_i \ge 0~ \text{and integer}\\
\end{align}
\end{split}\]
c = [25000,7000,9000]
A = [[53000,30000,41000],
[32000-1.5*21000,20000-1.5*10000,18000-1.5*23000 ],
[34000-.6*53000,12000-.6*30000,24000-.6*41000]]
b = [200000,0,0]
print(np.array(c).shape,np.array(A).shape,np.array(b).shape)
decision_variables = range(len(c))
constraints = range(np.array(A).shape[0])
m = Model("C5Q17")
x = []
for i in decision_variables:
x.append(m.addVar(lb = 0, vtype = GRB.INTEGER, name = 'x' + str(i)))
m.setObjective(quicksum(c[i] * x[i] for i in decision_variables) , GRB.MINIMIZE)
m.addConstrs((quicksum(A[j][i] * x[i] for i in decision_variables)
>= b[j] for j in constraints), "constraints")
m.optimize()
for var in m.getVars(): # descision variable
print(var.varName, '=', var.x, var.obj)
#for con in m.getConstrs(): # constraints
# print(con.ConstrName, ': slack =', con.slack,', shadow price=',
# con.pi,',', (con.RHS, con.SARHSLow, con.SARHSUp))
print("objective value =", m.objVal*1e6)
(3,) (3, 3) (3,)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 3 rows, 3 columns and 9 nonzeros
Model fingerprint: 0xcf860642
Variable types: 0 continuous, 3 integer (0 binary)
Coefficient statistics:
Matrix range [5e+02, 5e+04]
Objective range [7e+03, 2e+04]
Bounds range [0e+00, 0e+00]
RHS range [2e+05, 2e+05]
Found heuristic solution: objective 100000.00000
Presolve time: 0.00s
Presolved: 3 rows, 3 columns, 9 nonzeros
Variable types: 0 continuous, 3 integer (0 binary)
Explored 0 nodes (0 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 2 (of 2 available processors)
Solution count 1: 100000
Optimal solution found (tolerance 1.00e-04)
Best objective 1.000000000000e+05, best bound 1.000000000000e+05, gap 0.0000%
x0 = 4.0 25000.0
x1 = 0.0 7000.0
x2 = 0.0 9000.0
objective value = 100000000000.0
c = [25000,7000,9000]
A = [[53000,30000,41000],
[32000-1.5*21000,20000-1.5*10000,18000-1.5*23000 ],
[34000-.6*53000,12000-.6*30000,24000-.6*41000]]
b = [200000,0,0]
print(np.array(c).shape,np.array(A).shape,np.array(b).shape)
decision_variables = range(len(c))
constraints = range(np.array(A).shape[0])
m = Model("C5Q17")
x = []
for i in decision_variables:
x.append(m.addVar(lb = 0, vtype = GRB.CONTINUOUS, name = 'x' + str(i)))
m.setObjective(quicksum(c[i] * x[i] for i in decision_variables) , GRB.MINIMIZE)
m.addConstrs((quicksum(A[j][i] * x[i] for i in decision_variables)
>= b[j] for j in constraints), "constraints")
m.optimize()
for var in m.getVars(): # descision variable
print(var.varName, '=', var.x, var.obj)
#for con in m.getConstrs(): # constraints
# print(con.ConstrName, ': slack =', con.slack,', shadow price=',
# con.pi,',', (con.RHS, con.SARHSLow, con.SARHSUp))
print("objective value =", m.objVal*1e6)
(3,) (3, 3) (3,)
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 3 rows, 3 columns and 9 nonzeros
Model fingerprint: 0x921de87a
Coefficient statistics:
Matrix range [5e+02, 5e+04]
Objective range [7e+03, 2e+04]
Bounds range [0e+00, 0e+00]
RHS range [2e+05, 2e+05]
Presolve time: 0.01s
Presolved: 3 rows, 3 columns, 9 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 7.812500e+02 0.000000e+00 0s
3 8.2946176e+04 0.000000e+00 0.000000e+00 0s
Solved in 3 iterations and 0.02 seconds (0.00 work units)
Optimal objective 8.294617564e+04
x0 = 2.8895184135977336 25000.0
x1 = 1.0198300283286117 7000.0
x2 = 0.39660056657223786 9000.0
objective value = 82946175637.39377