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`

.

For the problem-based approach to this problem, see Mixed-Integer Linear Programming Basics: Problem-Based.

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 `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.

Ingot | Weight in Tons | %Carbon | %Molybdenum | Cost/Ton |
---|---|---|---|---|

1 | `5` | `5` | `3` | $350 |

2 | `3` | `4` | `3` | $330 |

3 | `4` | `5` | `4` | $310 |

4 | `6` | `3` | `4` | $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 | %Molybdenum | Cost/Ton |
---|---|---|---|

1 | `8` | `6` | $500 |

2 | `7` | `7` | $450 |

3 | `6` | `8` | $400 |

Scrap | `3` | `9` | $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 in tons of alloys **1**, **2**, and **3** you
purchase, and `x(8)`

is the quantity of scrap steel you
purchase.

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;

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

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.