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
Four ingots of steel are available for purchase. Only one of each ingot is available.
|Ingot||Weight in Tons||%Carbon||%Molybdenum||Cost/Ton|
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.
To formulate the problem, first decide on the control variables. Take variable
ingots(1) = 1 to mean that you purchase ingot
ingots(1) = 0 to mean that you do not purchase
the ingot. Similarly, variables
ingots(4) are binary variables indicating whether you
purchase ingots 2 through 4.
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.