Documentation

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

Mixed-Integer Linear Programming Basics

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.

IngotWeight (tons)%Carbon%MolybdenumCost/ton
1553$350
2343$330
3454$310
4634$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%MolybdenumCost/ton
186$500
277$450
368$400
Scrap39$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 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 matrices ([]).

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.

Was this topic helpful?