Accelerating the pace of engineering and science

# Documentation Center

• Trial Software

## Optimal Investments Via Binary Integer Programming

### Investments with Constraints

This example uses bintprog to solve an integer programming problem that is not obviously a binary integer programming problem. This is done by representing each nonbinary integer-valued variable as an appropriate sum of binary variables, and by using linear constraints carefully. While the example is not particularly realistic, it demonstrates a variety of techniques:

• How to formulate nonbinary integer programming problems

• How to formulate an objective and constraints

• How to use indicator variables (yi in the example)

### Problem Statement

There are five investment opportunities labeled 1, 2, 3, 4, and 5. The investments have the costs and payoffs listed in the following table.

1\$25\$5\$155
2\$35\$7\$254
3\$28\$6\$175
4\$20\$4\$137
5\$40\$8\$183

• The maximum total investment is \$125.

• The problem is to maximize profit, which is payoff minus cost.

• The payoff is the sum of the units bought times the payoff/unit.

• The cost per investment is the buy-in cost plus the cost/unit times the number of units if you buy at least one unit; otherwise, it is 0.

• The cost is the sum of the costs per investment.

It is convenient to formulate this problem using the indicator variables yi. Define these as yi = 1 when corresponding quantity variable xi is positive, and yi = 0 when xi = 0:

• xi = # units purchased of investment i

• yi = 1 if xi > 0, yi = 0 otherwise

• cost = Σ(Buy-in cost)i · yi + Σ(cost/unit)i · xi

• payoff = Σ(payoff/unit)i · xi

• profit = payoff – cost

In addition, there are several constraints on the investments:

• You may not invest in both 2 and 5.

• You may invest in 1 only if you invest in at least one of 2 and 3.

• You must invest in at least two of 3, 4, and 5.

• You may not invest more than the listed maximum number of units in each investment.

The constraints are represented in symbols as follows:

• y2 + y5 ≤ 1

• y1y2 + y3

• y3 + y4 + y5 ≥ 2

• x1 ≤ 5; x2 ≤ 4; x3 ≤ 5; x4 ≤ 7; x5 ≤ 3

• cost ≤ 125

### bintprog Formulation

To frame this problem as a binary integer programming problem, perform the following steps:

1. Represent each integer variable xi by three binary integer variables zi,j, j = 1,...,3, as follows:

xi = zi,1 + 2zi,2 + 4zi,3, i = 1,...,5.

Three zi,j suffice to represent xi, since each xi is assumed to be 7 or less. And, since x5 ≤ 3, z5,3 = 0.

2. Combine the variables y and z into a single vector t as follows:

 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 y1 y2 y3 y4 y5 z1,1 z1,2 z1,3 z2,1 z2,2 z2,3 z3,1 z3,2 z3,3 z4,1 z4,2 z4,3 z5,1 z5,2

3. Include the constraints yi = 0 if and only if all the corresponding zi,j = 0 as follows:

• yizi,1 + zi,2 + zi,3

• zi,1 + 2zi,2 + 4zi,3yi * (Max # unitsi)

These two inequalities enforce yi = 0 if and only if all the zi,j = 0, and they also enforce the maximum # units constraints.

4. As described in Maximizing an Objective, you find a maximum of an objective function by minimizing the negative of the objective function. So, to find the maximum profit, minimize the negative of the profit. The vector f that gives the negative of the profit in the form f'*t is

```f = [25,35,28,20,40,-10,-20,-40,-18,-36,-72,-11,-22,-44,...
-9,-18,-36,-10,-20]';```
• The first five entries in f represent the buy-in costs; these are incurred if the corresponding yi = 1.

• The next three entries, f(6), f(7), and f(8), represent the negative of payoff minus cost per unit for investment 1, –(\$15 – \$5), multiplied by 1, 2, and 4 respectively.

• The entries f(9), f(10), and f(11) represent the corresponding quantities for investment 2: –(\$25 – \$7), multiplied by 1, 2, and 4.

• f(12), f(13), and f(14) correspond to investment 3

• f(15), f(16), and f(17) correspond to investment 4

• f(18) and f(19) correspond to investment 5

5. Formulate all the constraints as inequalities of the form A · t ≤ b, as required in the bintprog formulation Binary Integer Programming Definition.

The following matrix A represents the constraints, along with the vector b:

```A = zeros(14,19);
A(1,1:19) = [25 35 28 20 40 5 10 20 7 14 28 ...
6 12 24 4 8 16 8 16];
A(2,1) = 1; A(2,6) = -1; A(2,7) = -1; A(2,8) = -1;
A(3,2) = 1; A(3,9) = -1; A(3,10) = -1; A(3,11) = -1;
A(4,3) = 1; A(4,12) = -1; A(4,13) = -1; A(4,14) = -1;
A(5,4) = 1; A(5,15) = -1; A(5,16) = -1; A(5,17) = -1;
A(6,5) = 1; A(6,18) = -1; A(6,19) = -1;
A(7,1) = -5; A(7,6) = 1; A(7,7) = 2; A(7,8) = 4;
A(8,2) = -4; A(8,9) = 1; A(8,10) = 2; A(8,11) = 4;
A(9,3) = -5; A(9,12) = 1; A(9,13) = 2; A(9,14) = 4;
A(10,4) = -7; A(10,15) = 1; A(10,16) = 2; A(10,17) = 4;
A(11,5) = -3; A(11,18) = 1; A(11,19) = 2;
A(12,2) = 1; A(12,5) = 1;
A(13,1) = 1; A(13,2) = -1; A(13,3) = -1;
A(14,3) = -1; A(14,4) = -1; A(14,5) = -1;
b = [125 0 0 0 0 0 0 0 0 0 0 1 0 -2]';```
• The first row of A represents the cost structure; no more than \$125 is available.

• Rows 2 through 6 represent yi ≤ Σj zi,j, i = 1,...,5.

• Rows 7 through 11 represent the maximum # units constraints. They also enforce yi = 1 when Σj zi,j > 0.

• Rows 12, 13, and 14 represent the other constraints on investments.

### bintprog Solution

bintprog solves the optimization problem as follows:

```[t fval exitflag output] = bintprog(f,A,b);
Optimization terminated.```

To examine the result, enter

```t',fval

ans =
Columns 1 through 10
0     0     1     1     0     0     0     0     0     0
Columns 11 through 19
0     1     0     1     1     1     1     0     0

fval =
-70```

You can easily see that the only positive values of y are y3 and y4. The values of x that correspond to these, x3 and x4, are

```t(12) + 2*t(13) + 4*t(14)
ans =
5

t(15) + 2*t(16) + 4*t(17)
ans =
7```

In other words, to obtain the maximum profit, \$70, invest in 5 units of 3 and 7 units of 4. By the way, this uses only

`28 + (5*6) + 20 + (7*4) = 106`

of the \$125 you had to invest, so there is \$19 left uninvested. You can also see this by checking the first constraint, [A*t](1):

```A(1,:)*t
ans =
106```