Binary Integer Programming Examples

On this page…
Example: Investments with Constraints

Example: 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 (y_i 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.

Investment	Buy-In Cost	Cost/Unit	Payoff/Unit	Max # Units
1	$25	$5	$15	5
2	$35	$7	$25	4
3	$28	$6	$17	5
4	$20	$4	$13	7
5	$40	$8	$18	3

• 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 y_i. Define these as y_i = 1 when corresponding quantity variable x_i is positive, and y_i = 0 when x_i = 0:

• x_i = # units purchased of investment i

• y_i = 1 if x_i > 0, y_i = 0 otherwise

• cost = Σ(Buy-in cost)_i · y_i + Σ(cost/unit)_i · x_i

• payoff = Σ(payoff/unit)_i · x_i

• 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:

• y₂ + y₅ ≤ 1

• y₁ ≤ y₂ + y₃

• y₃ + y₄ + y₅ ≥ 2

• x₁ ≤ 5; x₂ ≤ 4; x₃ ≤ 5; x₄ ≤ 7; x₅ ≤ 3

• cost ≤ 125

bintprog Formulation

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

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

   x_i = z_i,1 + 2z_i,2 + 4z_i,3, i = 1,...,5.

   Three z_i,j suffice to represent x_i, since each x_i is assumed to be 7 or less. And, since x₅ ≤ 3, z_5,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 y_i = 0 if and only if all the corresponding z_i,j = 0 as follows:

   • y_i ≤ z_i,1 + z_i,2 + z_i,3

   • z_i,1 + 2z_i,2 + 4z_i,3 ≤ y_i * (Max # units_i)

   These two inequalities enforce y_i = 0 if and only if all the z_i,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 y_i = 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 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 y_i ≤ Σ_j z_i,j, i = 1,...,5.

• Rows 7 through 11 represent the maximum # units constraints. They also enforce y_i = 1 when Σ_j z_i,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 y₃ and y₄. The values of x that correspond to these, x₃ and x₄, 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

Back to Top

Binary Integer Programming Algorithms

Least Squares (Model Fitting) Algorithms

© 1984-2012- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS