Main Content

Mixed-Integer Linear Programming Basics: Solver-Based

Open Live Script

这个例子展示了如何解决一个整数near problem. Although not complex, the example shows the typical steps in formulating a problem using the syntax forintlinprog.

For the problem-based approach to this problem, seeMixed-Integer Linear Programming Basics: Problem-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 athttps://doi.org/10.1287/inte.7.2.39.

Four ingots of steel are available for purchase. Only one of each ingot is available.

I n g o t W e i g h t i n T o n s % C a r b o n % M o l y b d e n u m C o s t T o n 1 5 5 3 $ 3 5 0 2 3 4 3 $ 3 3 0 3 4 5 4 $ 3 1 0 4 6 3 4 $ 2 8 0

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.

A l l o y % C a r b o n % M o l y b d e n u m C o s t T o n 1 8 6 $ 5 0 0 2 7 7 $ 4 5 0 3 6 8 $ 4 0 0 S c r a p 3 9 $ 1 0 0

制定问题,首先决定续rol variables. Take variablex(1) = 1to mean you purchase ingot1, andx(1) = 0to mean you do not purchase the ingot. Similarly, variablesx(2)throughx(4)are binary variables indicating whether you purchase ingots2through4.

Variablesx(5)throughx(7)are the quantities in tons of alloys1,2, and3that you purchase, andx(8)is the quantity of scrap steel that you purchase.

MATLAB® Formulation

Formulate the problem by specifying the inputs forintlinprog. The relevantintlinprogsyntax is:

[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

Create the inputs forintlinprogfrom the first (f) through the last (ub).

fis 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 inintcon, and give them a lower bound of0and an upper bound of1.

The problem has no linear inequality constraints, soAandbare empty matrices ([]).

A = []; b = [];

The problem has 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

Specify the constraints, which are Aeq*x = beq in matrix form.

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 Problem

Now that you have all the inputs, call the solver.

[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);
LP: Optimal objective value is 8125.600000. Cut Generation: Applied 3 mir cuts. Lower bound is 8495.000000. Relative gap is 0.00%. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).

View the solution.

x,fval
x =8×11.0000 1.0000 0 1.0000 7.2500 0 0.2500 3.5000
fval = 8.4950e+03

The optimal purchase costs $8,495. Buy ingots1,2, and4, but not3, and buy 7.25 tons of alloy1, 0.25 ton of alloy3, and 3.5 tons of scrap steel.

Setintcon = []to see the effect of solving the problem without integer constraints. The solution is different, and is not realistic, because you cannot purchase a fraction of an ingot.

Related Topics