Lecture Notes on Operations Research

LECTURE 7

INTERGER PROGRAMMING

Linear programming generally requires that the model variables are divisible. This implies
that each model variable can take on any non-negative, continuous solution value.

In certain decision problems, however, the divisibility assumption is unrealistic and

unacceptable. For instance, a solution requiring 1.34 bridges on a river system has no
practical meaning. In this case either 1 or 2 bridges must be assigned. Also in an assignment
problem, it is impossible to assign 1.22 people to 0.68 machines. These types of problems
require integer variables for the model variables. There are other types of problems that
require integer variables to take on values either one or zero. Integer programming technique
is applicable to such types of problems.

An integer programming model requires the following characteristics:

• a linear objective function
• a set of constraints
• non-negativity constraints for variables
• integer value constraints for certain variables

When the model requires all integer values, it is referred to as all-integer or pure integer
problem. When the model requires only certain variables to be integers, it is called a mixed-
integer programming problem. When the model requires only values of zero or one for the
decision variables, it is called a zero-one integer problem.

Integer Programming Solution Methods

There are several approaches to solving integer programming problems eg. the cutting plane
method and the branch-and-bound methods. We will present the branch-and-bound method -
the most widely used.

Branch-and Bound Solution Procedure

The branch-and-bound method is useful for solving integer, mixed-integer and zero-one
integer programming problems. The basic steps of the method are outlined as follows:
1. Solve the integer programming problem by the standard simplex method with the integer
restrictions relaxed (i.e. just as a normal LP problem).
2. Examine the optimal solution. If the basic variables that have integer restrictions have
integer solution values, the optimal integer solution is obtained. If one or more of the
basic variables do not satisfy integer requirements proceed to step 3.
3. The set of feasible integer solutions is branched into subsets (each subset comprising a
sub-problem). This branching is to eliminate continuous solutions that violate integer
requirements. Branching is achieved by introducing mutually exclusive constraints that
are necessary to satisfy integer requirements while making sure that no feasible integer
solution is excluded.
4. For each subset the optimal relaxed (LP) solution value of the objective function is the
upper bound. The best integer solution becomes the lower bound. Those subsets having
upper bounds that are less than the current lower bound are excluded from further
analysis. A feasible integer solution that is as good as or better than the upper bound for

Integer Programming by V. A. Temeng 1

 Lecture Notes on Operations Research

any subset is sought. If such a solution exists, it is optimal. If such a solution does not
exist a subset with the best upper bound is selected to branch on. Return to step 3.

Illustration of steps in the branch-and-bound method:

A manufacturing company wishes to determine how many of each of two different products it
should produce given limited resources in order to maximise total profit. The labour and
material requirements and the contribution to profit for each of the two products are as
follows:

Resource Requirement Profit

Labour Materials
hr/unit kg/unit $/unit
Product 1 4 6 36
Product 2 5 3 30

There are 20 hours of labour available daily for production. The company is limited to 18 kg
of material per day. The company wants to determine the number of each product to produce
in order to order to maximise total profit. Formulate and solve the problem as an integer
programming technique.

The problem is formulated as follows:

Max Z = 36X1+30X2
Subject to:

4X1+5X2  20
6X1+3X2  18
X1, X2 ≥ 0 and integer

The solution follows:

Augmentation:

Max Z = 36X1 + 30X2 + 0S1 + 0S2

Subject to:

4X1+5X2 + S1 = 20
6X1+3X2 + S2 = 18
X1, X2, S1, S2 ≥ 0

Cj 36 30 0 0
Cb basis bi X1 X2 S1 S2
0 S1 20 4 5 1 0
0 S2 18 6 3 0 1
Zj 0 0 0 0 0
Cj–Zj 36 30 0 0

Integer Programming by V. A. Temeng 2

 Lecture Notes on Operations Research

Cj 36 30 0 0
Cb basis bi X1 X2 S1 S2
0 S1 8 0 3 1 -4/6
36 X1 3 1 1/2 0 1/6
Zj 108 36 18 0 6
Cj–Zj 0 12 0 -6

Cj 36 30 0 0
Cb basis bi X1 X2 S1 S2
30 X2 8/3 0 1 1/3 -2/9
36 X1 5/3 1 0 -1/6 5/18
Zj 140 36 30 4 10/3
Cj–Zj 0 0 -4 -10/3

To apply the method subsets of the original problem are developed to determine the optimal
integer solution, as shown in Figure 7.1.

X1=1
X2=3
Z=126

X1=1 4
X2=16/5 X23
Z=132
X1=5/3 X1=0
2 X2=4
X2=8/3 X11
Z=140 X2≥4 Z=120

1 5
X1=2
X1≥2 X2=2
Z=132

3
Figure 7.1

Branch 1-2
Using the dual simplex method on the optimal relaxed LP tableau the sub-problem for this
branch is:
X2+1/3S1-2/9S2=8/3
X1-1/6S1+5/18S2=5/3
X11

If constraint 3 (branching constraint) is augmented it becomes:

X1+S3=1
S3 as a slack variable is the basic variable for this constraint.
Since X1 is a basic variable, the coefficient of X1 should be zero in the branching constraint to
make it appropriate. Recall that in the simplex method there should be an identity matrix

Integer Programming by V. A. Temeng 3

 Lecture Notes on Operations Research

associated with basic variable. This is done by multiplying the X1 (basic variable) row by -1
and adding to the S3 (basic variable) row.

The branching constraint then becomes:

1/6S1-5/18S2+S3=-2/3

Apply dual simplex to the resulting tableau as follows:

Cj 36 30 0 0 0
Cb basis bi X1 X2 S1 S2 S3
30 X2 8/3 0 1 1/3 -2/9 0
36 X1 5/3 1 0 -1/6 5/18 0
0 S3 -2/3 0 0 1/6 -5/18 1
Zj 140 36 30 4 10/3 0
Cj–Zj 0 0 -4 -10/3 0

The resulting tableau is:

Cj 36 30 0 0 0
Cb basis bi X1 X2 S1 S2 S3
30 X2 16/5 0 1 1/5 0 -4/5
36 X1 1 1 0 0 0 1
0 S2 12/5 0 0 -3/5 1 -18/5
Zj 132 36 30 6 0 12
Cj–Zj 0 0 -6 0 -12

This is the optimal tableau with X1=1, and X2=16/5.

Since X2 is not integer it should be branched on with the mutually exclusive constraints X23
and X2≥4 which will result in two sub-problems.

Branch 2-4
From the optimal tableau for branch 1-2 the constraints are:
X2+1/5S1-4/5S3=16/5
X1+S3=1
-3/5S1+S2-18/5S3=12/5, plus
X23 the branching constraint

Augmenting the branching constraint becomes:

X2+S4=3

To obtain an identity matrix corresponding to the branching constraint basic variable, the X2
(basic variable) constraint is multiplied by -1 and added to the S4 (basic variable) constraint to
become:
-1/5S1+4/5S3+S4=-1/5

The following tableau results:

Integer Programming by V. A. Temeng 4

 Lecture Notes on Operations Research

Cj 36 30 0 0 0 0
Cb basis bi X1 X2 S1 S2 S3 S4
30 X2 16/5 0 1 1/5 0 -4/5 0
36 X1 1 1 0 0 0 1 0
0 S2 12/5 0 0 -3/5 1 -18/5 0
0 S4 -1/5 0 0 -1/5 0 4/5 1
Zj 132 36 30 6 0 12 0
Cj–Zj 0 0 -6 0 -12 0

Using the dual simplex method the following tableau results:

Cj 36 30 0 0 0 0
Cb basis bi X1 X2 S1 S2 S3 S4
30 X2 3 0 1 0 0 0 0
36 X1 1 1 0 0 0 1 0
0 S2 3 0 0 0 1 -6 -3
0 S1 1 0 0 1 0 -4 -5
Zj 126 36 30 0 0 36 30
Cj–Zj 0 0 0 0 -36 -30

This optimal tableau yields an optimal integer solution. Therefore branch 2-4 is fathomed.
The optimal solution is X1=1 and X2=3 and maximum Z=126. The value 126 will therefore be
the lower bound to subsequent integer solutions to sub-problems.

The next sub-problem to solve is based on branch 2-5.

Branch 2-5
The constraints for this sub-problem are based on the optimal tableau for branch 1-2 and the
branching constraint. These are:

X2+1/5S1-4/5S3=16/5
X1+S3=1
-3/5S1+S2-18/5S3=12/5, plus
X2≥4

Convert branching constraint to a  by multiplying by -1 to become:

-X2-4, which is augmented to:
-X2+S5=-4
To obtain an identity matrix corresponding to the basic variable, S5, add the augmented
branching constraint to the X2 constraint. This becomes:

1/5S1-4/5S3+S5=-4/5

The following tableau results:

Integer Programming by V. A. Temeng 5

 Lecture Notes on Operations Research

Cj 36 30 0 0 0 0
Cb basis bi X1 X2 S1 S2 S3 S5
30 X2 16/5 0 1 1/5 0 -4/5 0
36 X1 1 1 0 0 0 1 0
0 S2 12/5 0 0 -3/5 1 -18/5 0
0 S5 -4/5 0 0 1/5 0 -4/5 1
Zj 132 36 30 6 0 12 0
Cj–Zj 0 0 -6 0 -12 0

Using the dual simplex method the following tableau results:

Cj 36 30 0 0 0 0
Cb basis bi X1 X2 S1 S2 S3 S5
30 X2 4 0 1 0 0 0 -1
36 X1 0 1 0 1/4 0 0 5/4
0 S2 6 0 0 -2/3 1 0 -9/2
0 S3 1 0 0 -1/4 0 1 -5/4
Zj 120 36 30 9 0 0 15
Cj–Zj 0 0 -9 0 0 -15

This tableau is optimal, therefore this branch 2-5 is fathomed. The optimal integer solution for
this branch is X1=0 and X2=4. The maximum value, Z=120 is an inferior solution, given that
the lower bound to all integer solutions at this stage is 126.

We now investigate branch 1-3 to see whether it will offer a better integer solution.

Branch 1-3
Branch 1-3 is based on the relaxed LP optimal tableau, therefore its constraints are:
X2+1/3S1-2/9S2=8/3
X1-1/6S1+5/18S2=5/3, plus
X1≥2

Convert branching constraint to a  by multiplying by -1 to become:

-X1-2, which is augmented to:
-X1+S6=-2

To obtain an identity matrix corresponding to the basic variable, S6, add the augmented
branching constraint to the X1 constraint. This becomes:
-1/6S1+5/18S2+S6=-1/3

The following simplex tableau results:

Cj 36 30 0 0 0
Cb basis bi X1 X2 S1 S2 S6
30 X2 8/3 0 1 1/3 -2/9 0
36 X1 5/3 1 0 -1/6 5/18 0
0 S6 -1/3 0 0 -1/6 5/18 1
Zj 140 36 30 4 10/3 0
Cj–Zj 0 0 -4 -10/3 0

Integer Programming by V. A. Temeng 6

 Lecture Notes on Operations Research

Using the dual simplex method the following tableau results:

Cj 36 30 0 0 0
Cb basis bi X1 X2 S1 S2 S6
30 X2 2 0 1 0 1/3 2
36 X1 2 1 0 0 0 -1
0 S1 2 0 0 1 -5/3 -6
Zj 132 36 30 0 10 24
Cj–Zj 0 0 0 -10 -24

This is the optimal tableau which yields all integers. The branch is therefore fathomed with
the solution values X1=2 and X2=2. The corresponding maximum value, Z=132 is the highest
value of all the sub-problems (branches).

Since all the sub-problems (branches) are fathomed and branch 1-3 gives the highest all
integer objective function value, the optimal integer solution is:

X1=2
X2=2

Lecture Assignment

Solve the following integer programming problem using the branch-and bound method.

Max Z = 4x1 + 6x2

Subject to:
2x1 + 4x2  10
4x1 + 3x2  12

x1, x2 ≥ 0 and integer

Integer Programming by V. A. Temeng 7