Mixed-Integer Linear Programming Basics: Problem-Based
This example shows how to solve a mixed-integer linear problem. Although not complex, the example shows the typical steps in formulating a problem using 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.
Problem Description
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 https://doi.org/10.1287/inte.7.2.39.
Four ingots of steel are available for purchase. Only one of each ingot is available.
Three grades of alloy steel and one grade of scrap steel are available for purchase. Alloy and scrap steels can be purchased in fractional amounts.
Formulate Problem
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 of scrap steel that you purchase.
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;
The problem has 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;
Solve Problem
Now that you have all the inputs, call the solver.
[sol,fval] = solve(steelprob);
Solving problem using intlinprog. Running HiGHS 1.7.0: Copyright (c) 2024 HiGHS under MIT licence terms Coefficient ranges: Matrix [3e-02, 6e+00] Cost [1e+02, 2e+03] Bound [1e+00, 1e+00] RHS [1e+00, 2e+01] Presolving model 3 rows, 8 cols, 24 nonzeros 0s 3 rows, 8 cols, 18 nonzeros 0s Solving MIP model with: 3 rows 8 cols (4 binary, 0 integer, 0 implied int., 4 continuous) 18 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 8125.6 inf inf 0 0 0 4 0.0s R 0 0 0 0.00% 8495 8495 0.00% 5 0 0 5 0.0s Solving report Status Optimal Primal bound 8495 Dual bound 8495 Gap 0% (tolerance: 0.01%) Solution status feasible 8495 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 0.00 (total) 0.00 (presolve) 0.00 (postsolve) Nodes 1 LP iterations 5 (total) 0 (strong br.) 1 (separation) 0 (heuristics) Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.
View the solution.
sol.ingots
ans = 4×1
1
1
0
1
sol.alloys
ans = 3×1
7.2500
0
0.2500
sol.scrap
ans = 3.5000
fval
fval = 8495
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.