Mixed-Integer Linear Programming Basics: Solver-Based

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.

`$\begin{array}{ccccc}Ingot& Weight\phantom{\rule{0.2777777777777778em}{0ex}}in\phantom{\rule{0.2777777777777778em}{0ex}}Tons& %\phantom{\rule{0.2777777777777778em}{0ex}}Carbon& %\phantom{\rule{0.2777777777777778em}{0ex}}Molybdenum& \frac{Cost}{Ton}\\ 1& 5& 5& 3& 350\\ 2& 3& 4& 3& 330\\ 3& 4& 5& 4& 310\\ 4& 6& 3& 4& 280\end{array}$`

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.

`$\begin{array}{cccc}Alloy& %\phantom{\rule{0.2777777777777778em}{0ex}}Carbon& %\phantom{\rule{0.2777777777777778em}{0ex}}Molybdenum& \frac{Cost}{Ton}\\ 1& 8& 6& 500\\ 2& 7& 7& 450\\ 3& 6& 8& 400\\ Scrap& 3& 9& 100\end{array}$`

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