Main Content

Mixed-Integer Linear Programming Basics: Solver-Based

Open Live Script

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 syntax for intlinprog.

For the problem-based approach to this problem, see Mixed-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 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

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 whether you purchase ingots 2 through 4.

Variables x(5) through x(7) are the quantities in tons of alloys 1, 2, and 3 that you purchase, and x(8) is the quantity of scrap steel that you purchase.

MATLAB® Formulation

Formulate the problem by specifying the inputs for intlinprog. The relevant intlinprog syntax is:

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

Create the inputs for intlinprog from the first (f) through the 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.

The problem has no linear inequality constraints, so A and b are 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);
Running HiGHS 1.7.0: 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.00 (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.

x,fval
x = 8×1

    1.0000
    1.0000
         0
    1.0000
    7.2500
         0
    0.2500
    3.5000


fval = 
8495

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 realistic, because you cannot purchase a fraction of an ingot.

Related Topics