Documentation

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.

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 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 intcon, and give them a lower bound of 0 and an upper bound of 1.

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.