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 in the syntax for intlinprog
.
Problem description
You want to blend a variety of 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 (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 x(1) = 1
to
mean you purchase ingot 1, and x(1) = 0
to mean you do not purchase
the ingot. Similarly, variables x(2)
through x(4)
are
binary variables indicating that you purchase ingots 2 through 4.
Variables x(5)
through x(7)
are
the quantities of alloys 1, 2, and 3 you
purchase, and x(8)
is the quantity of scrap steel
you purchase.
MATLAB formulation
Formulate the problem by specifying the inputs for intlinprog
.
The relevant intlinprog
syntax is as follows.
[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
Create the inputs for intlinprog
from first
(f
) through last (ub
).
f
is the vector of cost coefficients.
The coefficients representing the costs of ingots are the ingot weights
times their cost per ton.
f = [350*5,330*3,310*4,280*6,500,450,400,100];
The integer variables are the first four.
intcon = 1:4;
Tip
To specify binary variables, set the variables to be integers
in |
There are no linear inequality constraints, so A
and b
are
empty []
.
There are three equality constraints. The first is that the total weight is 25 tons.
5*x(1) + 3*x(2) + 4*x(3) + 6*x(4) + x(5) +
x(6) + x(7) + x(8) = 25
.
The second constraint is that the weight of carbon is 5% of 25 tons, or 1.25 tons.
5*0.05*x(1) + 3*0.04*x(2) + 4*0.05*x(3) + 6*0.03*x(4)
.
+ 0.08*x(5) + 0.07*x(6) + 0.06*x(7) + 0.03*x(8) = 1.25
The third constraint is that the weight of molybdenum is 1.25 tons.
5*0.03*x(1) + 3*0.03*x(2) + 4*0.04*x(3) + 6*0.04*x(4)
.
+ 0.06*x(5) + 0.07*x(6) + 0.08*x(7) + 0.09*x(8) = 1.25
In matrix form, Aeq*x = beq
, where
Aeq = [5,3,4,6,1,1,1,1; 5*0.05,3*0.04,4*0.05,6*0.03,0.08,0.07,0.06,0.03; 5*0.03,3*0.03,4*0.04,6*0.04,0.06,0.07,0.08,0.09]; beq = [25;1.25;1.25];
Each variable is bounded below by zero. The integer variables are bounded above by one.
lb = zeros(8,1); ub = ones(8,1); ub(5:end) = Inf; % No upper bound on noninteger variables
Solve the problem
Now that you have all the inputs, call the solver.
[x,fval] = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);
View the solution.
x,fval
x = 1.0000 1.0000 0 1.0000 7.2500 0 0.2500 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.
Set intcon = []
to see the effect of
solving the problem without integer constraints. The solution is different,
and is not sensible, because you cannot purchase a fraction of an
ingot.