This example shows how to solve a mixed-integer linear program. The example is not complex, but it shows typical steps in formulating a problem for the problem-based approach. For a video showing this example, see Solve a Mixed-Integer Linear Programming Problem using Optimization Modeling.

For the solver-based approach to this problem, see Mixed-Integer Linear Programming Basics: Solver-Based.

You want to blend steels with various chemical compositions to obtain 25 tons of steel with a specific chemical composition. The result should have 5% carbon and 5% molybdenum by weight, meaning 25 tons*5% = 1.25 tons of carbon and 1.25 tons of molybdenum. The objective is to minimize the cost for blending the steel.

This problem is taken from Carl-Henrik Westerberg, Bengt Bjorklund, and Eskil
Hultman, “*An Application of Mixed Integer Programming in a Swedish
Steel Mill*.” Interfaces February 1977 Vol. 7, No. 2 pp. 39–43,
whose abstract is at `http://interfaces.journal.informs.org/content/7/2/39.abstract`

.

Four ingots of steel are available for purchase. Only one of each ingot is available.

Ingot | Weight in Tons | %Carbon | %Molybdenum | Cost/Ton |
---|---|---|---|---|

1 | `5` | `5` | `3` | $350 |

2 | `3` | `4` | `3` | $330 |

3 | `4` | `5` | `4` | $310 |

4 | `6` | `3` | `4` | $280 |

Three grades of alloy steel are available for purchase, and one grade of scrap steel. Alloy and scrap steels can be purchased in fractional amounts.

Alloy | %Carbon | %Molybdenum | Cost/Ton |
---|---|---|---|

1 | `8` | `6` | $500 |

2 | `7` | `7` | $450 |

3 | `6` | `8` | $400 |

Scrap | `3` | `9` | $100 |

To formulate the problem, first decide on the control variables. Take variable
`ingots(1) = 1`

to mean that you purchase ingot
**1**, and
`ingots(1) = 0`

to mean that you do not purchase
the ingot. Similarly, variables `ingots(2)`

through
`ingots(4)`

are binary variables indicating whether you
purchase ingots **2** through **4**.

Variables `alloys(1)`

through `alloys(3)`

are the quantities in tons of alloys **1**,
**2**, and **3**
that you purchase. `scrap`

is the quantity in tons of scrap
steel that you purchase.

Create the optimization problem and the variables.

steelprob = optimproblem; ingots = optimvar('ingots',4,'Type','integer','LowerBound',0,'UpperBound',1); alloys = optimvar('alloys',3,'LowerBound',0); scrap = optimvar('scrap','LowerBound',0);

Create expressions for the costs associated with the variables.

weightIngots = [5,3,4,6]; costIngots = weightIngots.*[350,330,310,280]; costAlloys = [500,450,400]; costScrap = 100; cost = costIngots*ingots + costAlloys*alloys + costScrap*scrap;

Include the cost as the objective function in the problem.

steelprob.Objective = cost;

There are three equality constraints. The first constraint is that the total weight is 25 tons. Calculate the weight of the steel.

totalWeight = weightIngots*ingots + sum(alloys) + scrap;

The second constraint is that the weight of carbon is 5% of 25 tons, or 1.25 tons. Calculate the weight of the carbon in the steel.

carbonIngots = [5,4,5,3]/100; carbonAlloys = [8,7,6]/100; carbonScrap = 3/100; totalCarbon = (weightIngots.*carbonIngots)*ingots + carbonAlloys*alloys + carbonScrap*scrap;

The third constraint is that the weight of molybdenum is 1.25 tons. Calculate the weight of the molybdenum in the steel.

molybIngots = [3,3,4,4]/100; molybAlloys = [6,7,8]/100; molybScrap = 9/100; totalMolyb = (weightIngots.*molybIngots)*ingots + molybAlloys*alloys + molybScrap*scrap;

Include the constraints in the problem.

steelprob.Constraints.conswt = totalWeight == 25; steelprob.Constraints.conscarb = totalCarbon == 1.25; steelprob.Constraints.consmolyb = totalMolyb == 1.25;

Now that you have all the inputs, call the solver.

[sol,fval] = solve(steelprob);

Solving problem using intlinprog. LP: Optimal objective value is 8125.600000. Cut Generation: Applied 3 mir cuts. Lower bound is 8495.000000. Relative gap is 0.00%. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).

View the solution.

sol.ingots sol.alloys sol.scrap fval

ans = 1.0000 1.0000 0 1.0000 ans = 7.2500 0 0.2500 ans = 3.5000 fval = 8.4950e+03

The optimal purchase costs $8,495. Buy ingots **1**, **2**, and **4**, but not **3**, and buy 7.25 tons
of alloy **1**, 0.25 ton of alloy **3**, and 3.5 tons of scrap steel.