Equipment Assignment (IP)#
This problem is taken from Prof Jack Ponton’s Modelling, Simulation and Optimisation Online Course. Specifically, the LP relaxation is discussed in Section 5.4.2: Linear Programming Problems and the IP is discussed in Section 5.4.3: Mixed Integer Linear Programming (MILP) Problems.
A company wants to optimize profit through the sales of products (A, B, C)
Processing Time (in hours)
Product ↓ / Process → |
Reactor |
Crystalliser |
Centrifuge |
|---|---|---|---|
A |
0.8 |
0.4 |
0.2 |
B |
0.2 |
0.3 |
- |
C |
0.3 |
- |
0.1 |
Available Process Time (in minutes)
Process ↓ |
Time |
|---|---|
Reactor |
40 |
Crytallizer |
35 |
Centrifuge |
35 |
Profit on Sales (in $)
Product ↓ |
Profit |
|---|---|
A |
20 |
B |
6 |
C |
8 |
Sales limit (in units)
Product ↓ |
Limit |
|---|---|
C |
20 |
General Definition#
A function is made to handle the general definition of the problem, since the indices and most parameters remain the same, irrespective of how we treat the variables
# !pip install gana # uncomment and run to install Gana, if not in environment
from gana import Prg, V, P, I, sup
def general_def(name: str, itg: bool = True, rhs: list[int] = [20, 10, 5]) -> Prg:
p = Prg(name)
p.products = I('a', 'b', 'c')
p.processes = I('reactor', 'crystalliser', 'centrifuge')
p.profit = P(p.products, _=[20, 6, 8])
p.time = P(p.products, p.processes, _=[0.8, 0.4, 0.2, 0.2, 0.3, 0, 0.3, 0, 0.1])
p.tmax = P(p.processes, _=rhs)
p.nbatch = V(p.products, itg=itg)
p.cons_time = (
sum(p.time(product, p.processes) * p.nbatch(product) for product in p.products)
<= p.tmax
)
p.sales_lm = p.nbatch(p.c) <= 20
p.o = sup(sum(p.profit(product) * p.nbatch(product) for product in p.products))
return p
LP Relaxation#
Strictly speaking the number of batches processed should be a integer values. Nevertheless, let us solve the relaxed problem first.
p1 = general_def(name='lp_rlx', itg=False)
p1.show()
Mathematical Program for lp_rlx
Index Sets
\[\displaystyle {products} = \{ {{a}, {b}, {c}} \}\]
\[\displaystyle {processes} = \{ {{reactor}, {crystalliser}, {centrifuge}} \}\]
Objective
\[\displaystyle min \hspace{0.2cm} -20.0 \cdot {\mathbf{nbatch}}_{{a}} - 6.0 \cdot {\mathbf{nbatch}}_{{b}} - 8.0 \cdot {\mathbf{nbatch}}_{{c}}\]
s.t.
Inequality Constraint Sets
\[\displaystyle [0]\text{ }{\mathrm{{\mathrm{time}}}}_{{a},{processes}} \cdot {\mathbf{{\mathbf{{\mathbf{nbatch}}}}}}_{{a}} + {\mathrm{{\mathrm{time}}}}_{{b},{processes}} \cdot {\mathbf{{\mathbf{{\mathbf{nbatch}}}}}}_{{b}} + {\mathrm{{\mathrm{time}}}}_{{c},{processes}} \cdot {\mathbf{{\mathbf{{\mathbf{nbatch}}}}}}_{{c}} - {\mathrm{tmax}}_{{processes}} \leq 0\]
\[\displaystyle [1]\text{ }{\mathbf{{\mathbf{{\mathbf{nbatch}}}}}}_{{c}} - 20 \leq 0\]
Functions
\[\displaystyle [0]\text{ }-20.0 \cdot {\mathbf{nbatch}}_{{a}} - 6.0 \cdot {\mathbf{nbatch}}_{{b}} - 8.0 \cdot {\mathbf{nbatch}}_{{c}}\]
Optimizing the program
p1.opt()
📝 Generated lp_rlx.mps ⏱ 0.0007 s
Set parameter Username
Academic license - for non-commercial use only - expires 2026-08-01
Read MPS format model from file lp_rlx.mps
Reading time = 0.01 seconds
LP_RLX: 4 rows, 3 columns, 8 nonzeros
📝 Generated gurobipy model. See .formulation ⏱ 0.0133 s
Gurobi Optimizer version 12.0.3 build v12.0.3rc0 (win64 - Windows 11.0 (26100.2))
CPU model: 13th Gen Intel(R) Core(TM) i7-13700, instruction set [SSE2|AVX|AVX2]
Thread count: 16 physical cores, 24 logical processors, using up to 24 threads
Optimize a model with 4 rows, 3 columns and 8 nonzeros
Model fingerprint: 0x6d41737c
Coefficient statistics:
Matrix range [1e-01, 1e+00]
Objective range [6e+00, 2e+01]
Bounds range [0e+00, 0e+00]
RHS range [5e+00, 2e+01]
Presolve removed 1 rows and 0 columns
Presolve time: 0.00s
Presolved: 3 rows, 3 columns, 7 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 -6.0000000e+02 5.331617e+01 0.000000e+00 0s
2 -5.2500000e+02 0.000000e+00 0.000000e+00 0s
Solved in 2 iterations and 0.00 seconds (0.00 work units)
Optimal objective -5.250000000e+02
📝 Generated Solution object for lp_rlx. See .solution ⏱ 0.0000 s
✅ lp_rlx optimized using gurobi. Display using .output() ⏱ 0.0198 s
The number of batches (nbatch) have non-integer solutions.
p1.nbatch.output(asdict=True)
{(a,): 13.749999999999998, (b,): 15.0, (c,): 20.0}
With an objective value of:
p1.o.output(asfloat=True)
-525.0
IP Problem#
p2 = general_def(name='IP')
p2.opt()
📝 Generated IP.mps ⏱ 0.0005 s
Read MPS format model from file IP.mps
Reading time = 0.01 seconds
IP: 4 rows, 3 columns, 8 nonzeros
📝 Generated gurobipy model. See .formulation ⏱ 0.0085 s
Gurobi Optimizer version 12.0.3 build v12.0.3rc0 (win64 - Windows 11.0 (26100.2))
CPU model: 13th Gen Intel(R) Core(TM) i7-13700, instruction set [SSE2|AVX|AVX2]
Thread count: 16 physical cores, 24 logical processors, using up to 24 threads
Optimize a model with 4 rows, 3 columns and 8 nonzeros
Model fingerprint: 0xaaa99143
Variable types: 0 continuous, 3 integer (0 binary)
Coefficient statistics:
Matrix range [1e-01, 1e+00]
Objective range [6e+00, 2e+01]
Bounds range [0e+00, 0e+00]
RHS range [5e+00, 2e+01]
Found heuristic solution: objective -500.0000000
Presolve removed 1 rows and 0 columns
Presolve time: 0.00s
Presolved: 3 rows, 3 columns, 7 nonzeros
Variable types: 0 continuous, 3 integer (0 binary)
Root relaxation: objective -5.250000e+02, 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 -525.00000 0 1 -500.00000 -525.00000 5.00% - 0s
H 0 0 -510.0000000 -525.00000 2.94% - 0s
H 0 0 -524.0000000 -525.00000 0.19% - 0s
0 0 -525.00000 0 1 -524.00000 -525.00000 0.19% - 0s
Explored 1 nodes (2 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 24 (of 24 available processors)
Solution count 3: -524 -510 -500
No other solutions better than -524
Optimal solution found (tolerance 1.00e-04)
Best objective -5.240000000000e+02, best bound -5.240000000000e+02, gap 0.0000%
📝 Generated Solution object for IP. See .solution ⏱ 0.0000 s
✅ IP optimized using gurobi. Display using .output() ⏱ 0.0247 s
The solution obtained from the LP relaxation is pretty close to the actual integer solution, with a lower objective value
p2.output()
Solution for IP
Objective
\[\displaystyle min \hspace{0.2cm} -20.0 \cdot {\mathbf{nbatch}}_{{a}} - 6.0 \cdot {\mathbf{nbatch}}_{{b}} - 8.0 \cdot {\mathbf{nbatch}}_{{c}}=-524.0\]
Variables
\[\displaystyle {\mathbf{nbatch}}_{{a}}=14.0\]
\[\displaystyle {\mathbf{nbatch}}_{{b}}=14.0\]
\[\displaystyle {\mathbf{nbatch}}_{{c}}=20.0\]