1. Mixed integer linear programming (MILP)
Fantastic work with those constraints. We'll now look at mixed integer linear programming using SciPy.
2. Mixed integer linear programming
Mixed integer linear programming, or MILP, is an optimization technique used when constraint variables are integers, or discrete variables.
Let's look at it in action.
3. Gowns or tuxedos
A boutique design firm produces gowns and tuxedos.
There is weekly demand for at most 20 gowns, each at $1000, and for at most 12 tuxedos at $600.
To produce each gown, the firm must spend $110 in fabric, employ Mr S for 6 hours at $40/hour and have Ms T, the owner, finish up the garment in 3 hours at $35/hour. Correspondingly, for a tuxedo, fabric costs $75, Mr S needs 4 hours and Ms T 1 hour at the same rates.
4. Gowns or tuxedos
The constraints are that Mr S works for 40 hours per week maximum, whereas Ms T for at most 20 hours.
Let's find the optimum number of gowns and tuxedos that the firm should produce to maximize profit.
5. Objective and constraints
Let g be the number of gowns and t be the number of tuxedos that the firm will produce in one week. These will be integer values, making this an MILP problem.
The cost, C, of producing g gowns will be the sum of the cost of the fabric, and the wages of Mr S and Ms T. Since Ms T is the owner, their wages are an opportunity cost as they are spending their time sewing versus other responsibilities they might have as an owner.
The cost formula is then, 110g + 240g + 105 g + 75t + 160t + 35t. This summarizes down to 455g + 270t
6. Objective and constraints
The Revenue is R=1000g+600t.
Profit, Pi, is revenue minus cost. Here, that is 545g+330t.
Let's consider the constraints as well. Demand for gowns and tuxedos at most 20 and 12 respectively, shown here as g<=20 and t<=12. The supply constraints for Mr S and Ms T were maximum working hours of 40 and 20 respectively, shown here as 6g+4t<=40, 3g+t<=20.
7. MILP in SciPy
We are now ready to enter everything in SciPy and solve.
First we will import milp, Bounds and LinearConstraint from scipy.optimize.
We call milp. The first argument is the coefficients of the objective, or profit function, negated for maximizing.
Integrality is a boolean vector specifying whether variables are integers. Here both are, so the vector is [1, 1].
The bounds argument expects a Bounds object, which in turn expects vectors of lower and upper bounds for the variables.
Finally, the constraints argument expects a LinearConstraint object. It expects the matrix of coefficients, the first row is the Mr S's time to make a garment, and the second is Ms T's. ub which is the upper bound hours.
Note that if we have equality constraints, we may specify lb, the lower bound, and ub to be exactly the same.
8. MILP in SciPy
Let's print the results!
result.message is slightly different, but successfully is the key word.
The firm should produce 6 gowns and 1 tuxedo to maximize profit.
9. Integrality
Let's take one step back and look closer at the integrality argument.
What if we had neglected it?
Then the solver would search in continuous variables and the optimal solution would not necessarily be a whole number.
The solution would be 6.67 gowns and 0 tuxedos.
10. Consequences of omitting integrality
If we then rounded up to 7 and 0, the constraint for Mr S would not be satisfied as he would need to work 42 hours to make 7 gowns, which is over his 40 hour limit and a customer would not get their gown in time.
Suppose instead we truncated to 6 and 0. This would fit the hourly constraints for Mr S and Ms T. In fact, they both have time to do 1 Tuxedo.
Looking at the profit formula, the firm would have missed out on $330, about 10%, of the profit!
11. Let's Practice!
Let's practice!