Mixed-Integer Linear Programming Basics: Problem-Based - MATLAB & Simulink (original) (raw)
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.
IngotWeightinTons%Carbon%MolybdenumCostTon1553$3502343$3303454$3104634$280
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.
Alloy%Carbon%MolybdenumCostTon186$500277$450368$400Scrap39$100
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 = costIngotsingots + costAlloysalloys + costScrapscrap;
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 + carbonAlloysalloys + carbonScrapscrap;
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 + molybAlloysalloys + molybScrapscrap;
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.1: 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.01 (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.
ans = 3×1
7.2500
0
0.2500
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.