Mixed integer linear programming (MILP)

Introduction to Optimization in Python

Jasmin Ludolf

Content Developer

Mixed integer linear programming

  • MILP
  • Optimization technique used when constraint variables are discrete variables
Introduction to Optimization in Python

Gowns or tuxedos

  • Demand:

    • Gowns: At most $20$ at $\$ 1000$
    • Tuxedos: At most $12$ at $\$ 600$

  • Gown production:

    • Fabric $\$ 110$
    • Mr. S 6 hours at $\$40/h$
    • Ms. T 3 hours at $\$35/h$
  • Tuxedo production:
    • Fabric $\$ 75$
    • Mr. S 4 hours at $\$40/h$
    • Ms. T 1 hour at $\$35/h$

A couple dressed in a gown and a tuxedo

Introduction to Optimization in Python

Gowns or tuxedos

  • Constraints:
    • Mr. S at most 40 hours
    • Ms. T at most 20 hours

 

  • Find the optimum number of gowns and tuxedos to maximize profit

A person holding a red cloth and putting it on a mannequin to create a dress

Introduction to Optimization in Python

Objective and constraints

  • $g$: number of gowns in one week
  • $t$: number of tuxedos in one week

  • $C$: fabric cost + Mr. S wages + Mr. T opportunity cost

  • Opportunity cost: cost of choosing to sew versus other responsibilities

$C=110g+240g+105g+75t+160t+35t$

$C=455g+270t$

Cost Fabric Mr. S Ms. T
Gown $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
Tuxedo $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
Introduction to Optimization in Python

Objective and constraints

  • Revenue: $R=1000g+600t$
  • Cost: $C=455g+270t$
  • Profit: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Constraints:

    • Demand: $g\leq20$, $t\leq12$

    • Supply: $6g+4t\leq40$, $3g+t\leq20$

Introduction to Optimization in Python

MILP in SciPy

from scipy.optimize import milp, Bounds, LinearConstraint


result = milp([-545, -330],

              integrality=[1, 1],

              bounds=Bounds([0, 0], [20, 12]),

              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))
Introduction to Optimization in Python

MILP in SciPy

print(result.message)
print(f'The optimal number of gowns produced is: {result.x[0]:.2f}')
print(f'The optimal number of tuxedos produced is: {result.x[1]:.2f}') 

Optimization terminated successfully. (HiGHS Status 7: Optimal)
The optimal number of gowns produced is: 6.00
The optimal number of tuxedos produced is: 1.00
Introduction to Optimization in Python

Integrality

result = milp([-545, -330],  
              bounds=Bounds([0, 0], [20, 12]), 
              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))
...

The optimal number of gowns produced is: 6.67
The optimal number of tuxedos produced is: 0.00
Introduction to Optimization in Python

Consequences of omitting integrality

  • Proposed solution 6.67 gowns and 0.00 tuxedos $\rightarrow$

    • Round to 7 gowns and 0 tuxedos

      • Mr. S: $6g+4t=6\times7 + 4\times0 = 42$
      • $42 \gt 40$

    • Truncate to 6 gowns and 0 tuxedos

      • Mr. S: $6g+4t=6\times6 + 4\times0 = 36$
      • Ms. T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Missed out $330 (nearly 10%) in profit!
Introduction to Optimization in Python

Let's Practice!

Introduction to Optimization in Python

Preparing Video For Download...