Integer Programming

Branch & Bound Method

Example

Maximize z = x₁ + x₂

subject to
3x₁ + 2x₂ £ 12
x₂ £ 2

x₁, x₂ are integers ³ 0

Solution.

First, we solve the above problem by applying the simplex method.

After introducing slack variables, we have
3x₁ + 2x₂ + x₃ = 12
x₂ + x₄ = 2

where x₃ and x₄ are slack variables.

Initial basic feasible solution

x₁ = 0, x₂ = 0, and z = 0
x₃ = 12, x₄ = 2

Final Table

x₁ = 8/3, x₂ = 2
Since the solution obtained is not an integer solution, we choose x₁ = 8/3 (2 + 2/3), which has a fractional value and divide the problem into the following two sub-problems (problem - II and problem - III) by adding two new constraints x₁ £ 2 & x₁ ³ 3, because [x₁] = [2 + 2/3] = 2.

Problem - II

Maximize z = x₁ + x₂

subject to
3x₁ + 2x₂ £ 12
x₂ £ 2
x₁ £ 2

x₁, x₂ ³ 0

Introducing slack variables

3x₁ + 2x₂ + x₅ = 12
x₂ + x₆ = 2
x₁ + x₇ = 2

where x_5, x₆ and x₇ are slack variables.

Final Table

Optimal solution to problem - II is
x₁ = 2, x₂ = 2

Since all the variables in problem - II are integer valued, there is no need to branch this problem further.

Problem - III

Maximize z = x₁ + x₂

subject to
3x₁ + 2x₂ £ 12
x₂ £ 2
x₁ ³ 3

x₁, x₂ ³ 0

We use the two phase method to solve this problem.

Introducing slack, surplus & artificial variables

3x₁ + 2x₂ + x₈ = 12
x₂ + x₉ = 2
x₁ - x₁₀ + A₁ = 3

where:
x₈ and x₉ are slack variables.
x₁₀ is a surplus variable.
A₁ is an artificial variable.

Final Table

x₁ = 3, x₂ = 3/2
The solution obtained is not integer valued. Since [x₂] = [1 + 1/2] = 1, we divide the problem - III into two parts by adding two new constraints x₂ £ 1 & x₂ ³ 2. Thus, we form two sub-problems (problem - IV and problem - V).

Problem - IV

Maximize z = x₁ + x₂

subject to
3x₁ + 2x₂ £ 12
x₂ £ 2
x₁ ³ 3
x₂ £ 1

x₁, x₂ ³ 0

We use the two phase method to solve this problem.

Introducing slack, surplus & artificial variables

3x₁ + 2x₂ + x₁₁ = 12
x₂ + x₁₂ = 2
x₁ - x₁₃ + A₁ = 3
x₂ + x₁₄ = 1

where:
x₁₁, x₁₂ & x₁₄ are slack variables.
x₁₃ is a surplus variable.
A₁ is an artificial variable.

Final Table

x₁ = 10/3, x₂ = 1

Problem - V

Maximize z = x₁ + x₂

subject to
3x₁ + 2x₂ £ 12
x₂ £ 2
x₁ ³ 3
x₂ ³ 2

x₁, x₂ ³ 0

The solution to problem - V is infeasible. So we will not consider this problem.

But the solution to problem to problem - IV is not integer valued. Since [x₁] = [3 + 1/3] = 3, we divide the problem - IV into two parts by adding two new constraints x₁ £ 3 & x₁ ³ 4. Thus, we form two sub-problems (problem - VI and problem - VII).

Problem - VI

Maximize z = x₁ + x₂

subject to
3x₁ + 2x₂ £ 12
x₂ £ 2
x₁ ³ 3
x₂ £ 1
x₁ £ 3

x₁, x₂ ³ 0

Introducing slack, surplus & artificial variables

3x₁ + 2x₂ + x₁₅ = 12
x₂ + x₁₆ = 2
x₁ - x₁₇ + A₁ = 3
x₂ + x₁₈ = 1
x₁ + x₁₉ = 3

where:
x₁₅, x₁₆, x₁₈ and x₁₉ are slack variables.
x₁₇ is a surplus variable.
A₁ is an artificial variable.

Final Table

This problem has multiple optimal solution. As x₂ is zero, it enters into the basis.

The optimal solution is
x₁ = 3, x₂ = 1
Since all the variables in problem - VI are integer valued, there is no need to branch this problem further.

Problem - VII

Maximize z = x₁ + x₂

subject to
3x₁ + 2x₂ £ 12
x₂ £ 2
x₁ ³ 3
x₂ £ 1
x₁ ³ 4

x₁, x₂ ³ 0

Introducing slack, surplus & artificial variables

3x₁ + 2x₂ + x₂₀ = 12
x₂ + x₂₁ = 2
x₁ - x₂₂ + A₁ = 3
x₂ + x₂₃ = 1
x₁ - x₂₄ + A₂ = 4

where:
x₂₀, x₂₁ and x₂₃ are slack variables.
x₂₂ and x₂₄ are surplus variables.
A₁ and A₂ are artificial variables.

Final Table

The optimal solution is
x₁ = 4, x₂ = 0

Since all the variables in problem - VII are integer valued, there is no need to branch this problem further.

The history of the complete branch and bound solution is displayed by means of the following tree like diagram.

This chapter investigated the programming model in which the assumption of divisibility was weakened. You learned two algorithms to determine the optimal solution for an integer programming problem. One of these was the cutting plane algorithm devised by Gomory and the other was the branch & bound algorithm developed by Land & Doig.