SQQP3043 – Heuristic Techniques 1

CHAPTER 3:

BRANCH AND BOUND

INTRODUCTION

• The most common algorithm for solving integer programming

problems is the branch-and-bound method.

• It starts by first allowing non-integer solutions.

• If these values are integer valued, this must also be the solution to the
integer problem.

• If these variables are not integer valued, the feasible region is divided
by adding constraints restricting the value of one of the variables that
was not integer valued.

• The divided feasible region results in sub-problems that are then solved
- partitioned into smaller subsets of solutions.

• These smaller subsets can then be evaluated systematically until the

best solution is found.

• The branch and bound method uses a tree diagram of nodes and
branches to organize the solution partitioning.

• Bounds on the value of the objective function are found and used to
help determine which subproblems can be eliminated and when the
optimal solution has been found.

• If a solution is not optimal, a new subproblem is selected and

branching continues.
SQQP3043 – Heuristic Techniques 2

Six Steps in Solving IP Maximization Problems by Branch and Bound

1. Solve the original problem using LP. If the answer satisfies the integer
constraints, we are done. If not, this value provides an initial upper
bound.

2. Find any feasible solution that meets the integer constraints for use as
a lower bound. Usually, rounding down each variable will accomplish
this.

3. Branch on one variable from step 1 that does not have an integer value.
Split the problem into two subproblems based on integer values that
are immediately above or below the noninteger value.

4. Create nodes at the top of these new branches by solving the new
problem.

5. (a) If a branch yields a solution to the LP problem that is not

feasible, terminate the branch.

(b) If a branch yields a solution to the LP problem that is feasible,

but not an integer solution, go to step 6.

(c) If the branch yields a feasible integer solution, examine the

value of the objective function. If this value equals the upper bound, an
optimal solution has been reached. If it not equal to the upper bound,
but exceeds the lower bound, terminate this branch.

6. Examine both branches again and set the upper bound equal to the
maximum value of the objective function at all final nodes. If the
upper bound equals the lower bound, stop. If not, go back to step 3.

Note: Minimization problems involved reversing the roles of the

upper and lower bounds i.e. relaxed solutions are rounded up, and upper
and lower bounds are reversed.
SQQP3043 – Heuristic Techniques 3

Example 1:

(Render et al., 2006, page 453)

The Harrison Electric Company produces two products popular with

home renovators: old-fashioned chandeliers and ceiling fans. Both the
chandeliers and ceiling fans require a two-step production process
involving wiring and assembly. It takes about 2 hours to wire each
chandelier and 3 hours to wire a ceiling fan. Final assembly of the
chandeliers and fans requires 6 and 5 hours, respectively. The production
capability is such that only 12 hours of wiring time and 30 hours of
assembly time are available. If each chandelier produced nets the firm
US$7 and each fan US$6, formulate the Harrison’s production using LP
model.

Maximize profit z = $7X1 + $6X2

subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30
where
X1 = number of chandeliers produced
X2 = number of ceiling fans produced

The optimal noninteger solution is:

X1 = 3.75 chandeliers, X2 = 1.5 ceiling fans

profit = $35.25

Since X1 and X2 are not integers, this solution is not valid. The profit value
of $35.25 will provide the initial upper bound.

We can round down to X1 = 3, X2 = 1, profit = $27, which provides a

feasible lower bound.
SQQP3043 – Heuristic Techniques 4

The problem is now divided into two subproblems:

Subproblem A
Maximize profit = $7X1 + $6X2
subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30
X1 ≥4

Subproblem B
Maximize profit = $7X1 + $6X2
subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30
X1 ≤3

If you solve both subproblems:

Subproblem A’s
optimal solution: [X1 = 4, X2 = 1.2, profit = $35.20]

Subproblem B’s
optimal solution: [X1 = 3, X2 = 2, profit = $33.00]

We have completed steps 1 to 4 of the branch and bound method

SQQP3043 – Heuristic Techniques 5

Harrison Electric’s first branching: subproblems A and B

Next Branch (C)

Subproblem A

X1 = 4 Infeasible (Noninteger) Solution

X2 = 1.2 Upper Bound = $35.20
Lower Bound = $33.00
P = 35.20

Next Branch (D)

X1 = 3.75 Upper Bound = $35.25
X2 = 1.5 Lower Bound = $27.00 (From
P = 35.25 Rounding Down)
Subproblem B

X1 = 3
X2 = 2
P = 33.00
Stop This Branch
Solution Is Integer, Feasible
Provides New Lower Bound of $33.00

Subproblem A has branched into two new subproblems, C and D:

Subproblem C
Maximize profit = $7X1 + $6X2
subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30
X1 ≥4
X2 ≥2

Subproblem D
Maximize profit = $7X1 + $6X2
subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30
X1 ≥4
X2 ≤1

Subproblem C has no feasible solution because the all the constraints

cannot be satisfied. We terminate this branch and do not consider this
solution. Subproblem D’s optimal solution is X1 = 4.17, X2 = 1, profit =
$35.16. This noninteger solution yields a new upper bound of $35.16.
Finally, we create subproblems E and F
SQQP3043 – Heuristic Techniques 6

Subproblem E
Maximize profit = $7X1 + $6X2
subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30 Optimal solution to E:
X1 ≥4 X1 = 4, X2 = 1, profit = $34
X1 ≤4
X2 ≤1
Subproblem D
Maximize profit = $7X1 + $6X2
subject to 2X1 + 3X2 ≤ 12
6X1 + 5X2 ≤ 30 Optimal solution to F:
X1 ≥4 X1 = 5, X2 = 0, profit = $35
X1 ≥5
X2 ≤1

• The stopping rule for the branching process is that we continue until
the new upper bound is less than or equal to the lower bound or no
further branching is possible.

• The later case applies here since both branches yielded feasible integer
solutions.

• The optimal solution is subproblem F’s node.

• Harrison Electric’s full branch and bound solution:

 SQQP3043 – Heuristic Techniques 7

Subproblem C

No
Feasible
Solution
Region
Subproblem A Subproblem E

X1 = 4 X1 = 4
X2 = 1.2 X2 = 1 Feasible, Integer
P = 35.20 P = 34.00 Solution
Subproblem D

X1 = 3.75 X1 = 4.17
X2 = 1.5 X2 = 1
P = 35.25 P = 35.16
Subproblem B Subproblem F

X1 = 3 Upper Bound X1 = 5
X2 = 2 = $35.25 X2 = 0
P = 33.00 Lower Bound P = 35.00
= $27.00
Optimal
Solution
SQQP3043 – Heuristic Techniques 8

• Key aspects of the branch-and-bound method for solving pure IPs

o If it is unnecessary to branch on a sub-problem, we say that it is
fathomed.

• These three situations (for a max problem) result in a sub-problem

being fathomed
o The sub-problem is infeasible, thus it cannot yield the optimal
solution to the IP.
o The sub-problem yield an optimal solution in which all variables
have integer values. If this optimal solution has a better z-value
than any previously obtained solution that is feasible in the IP, than
it becomes a candidate solution, and its z-value becomes the
current lower bound (LB) on the optimal z-value for the IP.
o The optimal z-value for the sub-problem does not exceed (in a max
problem) the current LB, so it may be eliminated from
consideration.

• A sub-problem may be eliminated from consideration in these

situations
o The subproblem is infeasible.
o The LB is at least as large as the z-value for the subproblem

• Two general approaches are used to determine which subproblem

should be solved next.
o The most widely used is LIFO.
▪ LIFO leads us down one side of the branch-and-bound
tree and quickly find a candidate solution and then we
backtrack our way up to the top of the other side
▪ The LIFO approach is often called backtracking.
o The second commonly used approach is jumptracking.
▪ When branching on a node, the jumptracking method
solves all the problems created by branching.

• In this chapter, we will solve three types of problems i.e. (1) Knapsack
problem, (2) machine scheduling problem and (3) traveling
salesperson problem (TSP) by the branch and bound method.
SQQP3043 – Heuristic Techniques 9

Knapsack Problem

• Knapsack problem is an IP with a single constraint, where each

variable must equal 0 or 1.

Max z = c1x1 + c2x2 + … + cnxn

s.t. a1x1 + a2x2 + … + anxn ≤ b
xi = 0 or 1 (i = 1, 2, …, n)

• ci is the benefit obtained if item i is chosen, b is the amount of an

available resource, and ai is the amount of the available resource used
by item i.

• When knapsack problems are solved by the branch-and-bound method,

two aspects of the method greatly simplify.
o Due to each variable equaling 0 or 1, branching on xi will yield
in xi =0 and an xi =1 branch.
o The LP relaxation may be solved by inspection.

• LP relaxation may be solved by inspection:

ci
o Find the best item that has largest value of  benefit item i
ai
earns for each unit of the resource used by item i.

o Put the best item in the knapsack, the second best item and so on
until the best remaining item will overfill the knapsack.
SQQP3043 – Heuristic Techniques 10

Example 2

Max z = 40x1 + 80x2 + 10x3 + 10x4 + 4x5 + 20x6 + 60x7

s.t. 40x1 + 50x2 + 30x3 + 10x4 + 10x5 + 40x6 + 30x7 ≤ 100
xi = 0 or 1 (i = 1, 2, …, 7)

Solution:
SQQP3043 – Heuristic Techniques 11

Example 3

Recall the Stocko capital budgeting problem in Chapter 1. Solve the LP

relaxation of this problem using inspection. Then, use the branch and
bound method to solve the problem.

Max z = 16x1 + 22x2 + 12x3 + 8x4

s.t. 5x1 + 7x2 + 4x3 + 3x4 ≤ 14
xj = 0 or 1

Relaxation of LP using inspection:

SQQP3043 – Heuristic Techniques 12

Branch and Bound:

Subproblem 1
z = 44
x1 = x2 = 1
x3 = 1/2

x3 = 0 x3 = 1

Subproblem 2 Subproblem 3
z = 43 5/7
x1 = x3 = 1
x2 = 5/7
x4 = 0
SQQP3043 – Heuristic Techniques 13

Remarks:

• We used LIFO approach to determine which sub-problem should be

solved. (LIFO – solve the most recently created subproblems).

• We arbitrarily chose the sub-problem 3 before sub-problem 2. To

solve sub-problem 3, we first set x3 = 1 and then solved the resulting
knapsack problem. After setting x3 = 1, x1 = 1, x2 = 5/7, x4 = 0, z =
43 5/7. Other sub-problems were solved similarly.

• Sub-problem 4 yielded the candidate solution x1 = x3 = x4 = 1, z = 36.

• Sub-problem 6 yielded a candidate solution with z = 42. Thus, sub-

problem 4 was eliminated from consideration, and the LB was updated
to 42.

• Sub-problem 7 was infeasible.

• Sub-problem 8 was eliminated because its z-value (z = 38) did not

exceeded the current LB of 42.

• Sub-problem 9 has a z-value of 42 6/7. Since the z-value for any all-
integer solution must also be an integer, this meant that branching on
sub-problem 9 could never yield a z-value larger than 42. Thus, further
branching on sub-problem 9 could not beat the current LB of 42, and
sub-problem 9 was eliminated from consideration.
SQQP3043 – Heuristic Techniques 14

Machine Scheduling Problem

Jobs: J1 , J2 , ..., Jn

• In this problem, we consider a single machine to process a number of

jobs. The time to complete each job and the time at which each job
must be completed are known.

• The objective of this problem is to find an ordering of the jobs that can
minimize the total delay of the jobs.

• Assumptions:
▪ The machine is always available throughout the scheduling period.
▪ The machine cannot process more than one job at a time.
▪ Each job must spend on the machine a prescribed length of time.

xij  1 if job i is the jth job to be processed

0 otherwise

xi
4
3
2
1

x21 x32 x13 .......

• Requirements that may restrict the feasibility of schedules:

▪ precedence constraints
▪ no preemptions
▪ release dates
▪ deadlines
SQQP3043 – Heuristic Techniques 15

• Branch and bound for single machine scheduling contains n! schedules

(n is number of jobs).

*, *, *, *

1, *, *, * 2, *, *, * ………... n, *, *, * 1st Level

2nd Level
1, 2, *, * 1, 3, *, * ………...

………...

• Branching rule:
▪ k-1 level, j1 , ... , jk-1 are scheduled,
▪ jk need to be considered if no job to be scheduled cannot be
processed before the release time of jk
SQQP3043 – Heuristic Techniques 16

Example 4:

(Please refer Winston (1994) page 520)

Four jobs must be processed on a single machine. The time required to
process each job and the date the job is due are shown in the table below.
The delay of a job is the number of days after the due date that a job is
completed (if a job is completed on time or early, the job’s delay is zero).
In what order should the jobs be processed to minimize the total delay of
the four jobs.

Job Time required to Due date

complete job (days)
1 6 End of day 8
2 4 End of day 4
3 5 End of day 12
4 8 End of day 16

Solution:

Suppose the jobs are processed in the following order: Job 1, 2, 3 and 4.
The delays occur is shown in the table below:

Job Completion time of job Delay of job

1 6 0
2 6 + 4 = 10 10 – 4 = 6
3 6 + 4 + 5 = 15 15 – 12 = 3
4 6 + 4 + 5 + 8 = 23 23 – 16 = 7

• The branch and bound approach begins by partitioning all solutions

according to the job that is last processed.

x14 = 1, x24 = 1, x34 = 1, or x44 = 1

• Create four branches with nodes 1 – 4 and obtain a lower bound on the
total delay (D) associated with the node.

• For example, if x44 = 1, we know that job 4 is the last job to be

processed. In this case, job 4 will be completed at the end of the day
SQQP3043 – Heuristic Techniques 17

6 + 4 + 5 + 8 = 23, 23 – 16 = 7 days late

Thus, any schedule having x44 = 1 must have D ≥ 7.

x14 = 1 x44 = 1
x24 = 1 x34 = 1
Node 1 Node 2 Node 3 Node 4
D ≥ 15 D ≥ 19 D ≥ 11 D≥7

• In this example, we used jumptracking approach and branch on the

node that has smallest bound on D: node 4.

• Any job sequence associated with node 4 must have:

x13 = 1, x23 = 1, or x33 = 1

• Branching on node 4 yields nodes 5 – 7 with new lower bound of the

total delay.

• For example, at node 7, we know that job 4 will processed last and
delayed by 7 days and job 3 will be the third job processed. Thus, job
3 will be completed after 6 + 4 + 5 = 15 days and will be 15 – 12 = 3
days late. Any sequence associated with node 7 must have D ≥ 7 + 3 =
10 DAYS.

x14 = 1 x44 = 1
x24 = 1 x34 = 1
Node 1 Node 2 Node 3 Node 4
D ≥ 15 D ≥ 19 D ≥ 11 D≥7

x13 = 1 x33 = 1
x23 = 1
Node 5 Node 6 Node 7
D ≥ 14 D ≥ 18 D ≥ 10
SQQP3043 – Heuristic Techniques 18

• We still do not have any reason to eliminate any of nodes 1 – 7 from

consideration, so we again branch on a node.

• Jumptracking approach directs us to branch on node 7 where job

sequence of node 7 must have either job 1 or job 2 as the second job
processed.

x14 = 1 x44 = 1
x24 = 1 x34 = 1
Node 1 Node 2 Node 3 Node 4
D ≥ 15 D ≥ 19 D ≥ 11 D≥7

x13 = 1 x33 = 1
x23 = 1
Node 5 Node 6 Node 7
D ≥ 14 D ≥ 18 D ≥ 10

x12 = 1 x22 = 1
Node 8 Node 9
D = 12 D = 16

• Node 9 corresponds to processing the job in the order 1-2-3-4. This

sequence yields a total delay of 7 (for job 4) + 3 (for job 3) + (6 + 4 –
4) (for job 2) + 0 (for job 1) = 16 days.

• Node 9 is a feasible sequence and may be considered as a candidate

solution having D = 16. Any node that has total delay more than 16
days can be eliminated.

• Node 8 corresponds to the sequence 2-1-3-4. This sequence has a total

delay of 7 (for job 4) + 3 (for job 3) + (4 + 6 – 8) (for job 1) + 0 (for
job 2) = 12 days.

• Node 8 is a feasible sequence and may be viewed as a candidate

solution with D = 12. Since node 8 is better than node 9, node 9 s
eliminated from consideration.
 SQQP3043 – Heuristic Techniques 19

• Similarly, node 5 (D ≥ 14), node 6 (D ≥ 18), node 1 (D ≥ 15), and node

2 (D ≥ 19) can be eliminated.

• Node 3 cannot be eliminated yet because it is still possible for node 3

to yield a sequence having D = 11. Thus, node is branched which
associated with x13 = 1, x23 = 1, or x43 = 1.

x14 = 1 x44 = 1
x24 = 1 x34 = 1
Node 1 Node 2 Node 3 Node 4
D ≥ 15 D ≥ 19 D ≥ 11 D≥7

x13 = 1 x13 = 1 x33 = 1

x23 = 1 x43 = 1 x23 = 1
Node 10 Node 11 Node12 Node 5 Node 6 Node 7
D ≥ 21 D ≥ 25 D ≥ 13 D ≥ 14 D ≥ 18 D ≥ 10

x12 = 1 x22 = 1
Node 8 Node 9
D = 12 D = 16

• For node 10, D ≥ (delay from processing job 3 last) + (delay from
processing job 1 third) = 11 + (6 + 4 + 8 – 8) = 21. Since any sequence
associated with node 10 must have D ≥ 21 and we have a candidate
with D = 12, node 10 is eliminated.

• For node 11, D ≥ (delay from processing job 3 last) + (delay from
processing job 2 third) = 11 + (6 + 4 + 8 – 4) = 25. Any sequence
associated with node 11 must have D ≥ 25, node 11 is eliminated.

• Finally, for node 12, D ≥ (delay from processing job 3 last) + (delay
from processing job 4 third) = 11 + (6 + 4 + 8 – 16) = 13. Any
sequence associated with node 12 must have D ≥ 13, node 12 is
eliminated.
SQQP3043 – Heuristic Techniques 20

• With the exception of node 8, every node has been eliminated from
consideration. Node 8 yields the delay-minimizing sequence x14 = x24
= x34 = x44 = 1.

• Thus, the jobs should be processed in the order 2-1-3-4 with a total
delay of 12 days resulting.
SQQP3043 – Heuristic Techniques 21

Traveling Saleperson Problem (TSP)

• Starting from his home, a salesman wishes to visit each of (n −1) other
cities and return home at minimal cost. He must visit each city exactly
once and it costs cij to travel from city i to city j. What route should he
select?

• Let
xij  1 if he goes from city i to city j,
0 otherwise

We may be tempted to formulate his problem as the assignment

problem:

N N

Minimize  c
i 1 j 1
ij xij

subject to: x
i 1
ij  1, (j = 1, 2, ..., N)
N

x
j 1
ij  1, (i = 1, 2, ..., N)
u i  u j  Nx ij  N  1 (for i ≠ j; i = 2, 3, .., N; j = 2, ..., N)
xij  0 or 1, x j  0

• The constraints require that the salesman must enter and leave each
city exactly once.

• TSP can be solved using branch and bound method.

• Apply Hungarian method to the TSP in finding optimal solution:

o Step 1: Find the minimum element in each row of the m × m

cost matrix and subtract from each cost the minimum cost in
its row. Next, find the minimum cost in each column and
subtract from each cost the minimum cost in its column.
SQQP3043 – Heuristic Techniques 22

o Step 2: Draw the minimum number of lines (horizontal and/or

vertical) that are needed to cover all the zeros. If m lines are
required, an optimal solution is available among the covered
zeros. If fewer than m lines, proceed to Step 3.

o Step 3: Find the smallest nonzero element (call its value k)

that is uncovered by the lines drawn in Step 2. Subtract k from
each uncovered element and add k to each element that is
covered by two lines. Return to Step 2.

Example 5:

Find the optimal solution for the given table below.

14 5 8 7
2 12 6 5
7 8 3 9
2 4 6 10

Solution:

Find the row minimum

Row
minimum
14 5 8 7 5
2 12 6 5 2
7 8 3 9 3
2 4 6 10 2

Subtract each element in the row with row minimum

9 0 3 2
0 10 4 3
4 5 0 6
0 2 4 8
Column
0 0 0 2
minimum
SQQP3043 – Heuristic Techniques 23

After subtracting each element in column with column minimum, covered

all the zeros with minimum lines.

9 0 3 0
0 10 4 1
4 5 0 4
0 2 4 6

Since fewer than four lines are required to cover all the zeros, proceed to
Step 3. The smallest uncovered element is 1, so subtract 1 from each
uncovered element and add 1 to each twice-covered element.

10 0 3 0
0 9 3 0
5 5 0 4
0 1 3 5
SQQP3043 – Heuristic Techniques 24

Example 6:

(Please refer Winston (1994) page 522)

Joe State lives in Gary, Indiana. He owns insurance agencies in Gary, Fort
Wayne, Evansville, Terre Haute and South Bend. Each December, he
visits each of his insurance agencies. The distance between each if his
agencies (in miles) is shown in the table below. What order of visiting his
agencies will minimize the total distance traveled?

Fort Terre South

City Gary Evansville
Wayne Haute Bend
1 Gary 0 132 217 164 58
2 Fort Wayne 132 0 290 201 79
3 Evansville 217 290 0 113 303
4 Terre Haute 164 201 113 0 196
5 South Bend 58 79 303 196 0

Solution:

• Define

xij  1 if Joe goes from city i to city j,

0 otherwise

For i ≠ j,
cij  distance between cities i and j
cii  M, where M is a large positive number

• Supposed this assignment problem is solved with the solution x14 = x24
= x45 = x53 = x31 = 1. This solution can be written 1-2-4-5-3-1. An
itinerary that begins and ends at the same city and visits each city once
is called a tour.

• If the solution to the preceding asignment problem yields a tour, it is

the optimal solution to the TSP. Unfortunately, the optimal solution to
the assignment problem need not be a tour.
SQQP3043 – Heuristic Techniques 25

• For example, the optimal solution to the assignment problem might be

x15 = x21 = x34 = x43 = x52 = 1. This solution contains two subtours.

3 4

2 5

• A subtour is a round trip that does not pass through all cities. The two
subtours are 1-5-2-1 and 3-4-3.

• If we could exclude all feasible solutions that contain subtours and

then solve the assignment problem, we would obtain the optimal
solution to the TSP.

• Branch and bound approach is the most efficient approach for solving
a TSP.

• To begin, we solve the preceding assignment problem, in which, for i

≠ j, the cost c ij is the distance between cities i and j and cii  M (this
prevents a person in a city from being assigned to visit that city itself).

City 1 2 3 4 5
1 M 132 217 164 58
2 132 M 290 201 79
3 217 290 M 113 303
4 164 201 113 M 196
5 58 79 303 196 M
Cost matrix of subproblem 1

• The optimal solution (apply Hungarian method) for this example is

x15 = x21 = x34 = x43 = x52 = 1, z = 495 (subproblem 1). However, it
contains two subtours (1-5-2-1 and 3-4-3) and cannot be the optimal
solution to a TSP.
SQQP3043 – Heuristic Techniques 26

• Branch on subproblem 1. Choose to exclude the subtour 3-4-3 (x34 = 0

or x43 = 0).

Subproblem 1
z = 495
x15 = x21 = x34 =
x43 = x52 = 1
x34 = 0 x43 = 0

Subproblem 2 Subproblem 3
z = 652 z = 652
x14 = x25 = x31 = x13 = x25 = x34 =
x43 = x52 = 1 x41 = x52 = 1

• Apply Hungarian method to cost matrix of subproblem 2 in order to

find optimal solution to subproblem 2. The optimal solution for
subproblem 2 is z = 652, x14 = x25 = x31 = x43 = x52 = 1 which includes
the subtours 1-4-3-1 and 2-5-2. This solution is not optimal.

City 1 2 3 4 5
1 M 132 217 164 58
2 132 M 290 201 79
3 217 290 M M 303
4 164 201 113 M 196
5 58 79 303 196 M
Cost matrix of subproblem 2

• Branch on subproblem 2 (subproblem 4 and subproblem 5) in an effort

to exclude the subtour 2-5-2 where either x25 or x52 equals zero.

• Following the LIFO rule, next solve subproblem 4 or subproblem 5.

Randomly choose subproblem 4. Apply Hungarian method to the cost
matrix of subproblem 4. We obtain the optimal solution z = 668, x15 =
x24 = x31 = x43 = x52 = 1.
SQQP3043 – Heuristic Techniques 27

City 1 2 3 4 5
1 M 132 217 164 58
2 132 M 290 201 M
3 217 290 M M 303
4 164 201 113 M 196
5 58 79 303 196 M
Cost matrix of subproblem 4

• This solution contains no subtours and yields the tour 1-5-2-4-3-1.

Thus, subproblem 4 yields a candidate solution with z = 668. Any
node that cannot yield a z-value < 668 may be eliminated from
consideration.

Subproblem 1
z = 495
x15 = x21 = x34 =
x43 = x52 = 1
x34 = 0 x43 = 0

Subproblem 2 Subproblem 3
z = 652 z = 652
x14 = x25 = x31 = x13 = x25 = x34 =
x43 = x52 = 1 x41 = x52 = 1

Subproblem 4 Subproblem 5
z = 668 z = 704
x15 = x24 = x31 = x14 = x43 = x32 =
x43 = x52 = 1 x25 = x51 = 1
candidate sol. UB = 668

• Next, solve subproblem 5, applying Hungarian method to the cost

matrix of subproblem 5. The optimal solution to subproblem 5 is z =
704, x14 = x43 = x32 = x25 = x51 = 1. This solution is a tour, but z = 704
> 668. Thus, subproblem 5 is eliminated from consideration.
SQQP3043 – Heuristic Techniques 28

City 1 2 3 4 5
1 M 132 217 164 58
2 132 M 290 201 79
3 217 290 M M 303
4 164 201 113 M 196
5 58 M 303 196 M
Cost matrix of subproblem 5

• Continue with subproblem 3. We found that the optimal solution to

subproblem 3 is z = 652, x13 = x25 = x34 = x41 = x52 = 1. This solution
contains the subtours 1-3-4-1 and 2-5-2.

City 1 2 3 4 5
1 M 132 217 164 58
2 132 M 290 201 79
3 217 290 M 113 303
4 164 201 M M 196
5 58 79 303 196 M
Cost matrix of subproblem 3

• Since 652 < 668, it is still possible for subproblem 3 to yield a solution
with no subtours that beats z = 668. Thus, branch on subproblem 3
(subproblem 6 and 7) in an effort to exclude the subtours with x25 = 0
or x52 = 0.

• Using LIFO rule, choose to solve subproblem 6 using Hungarian

method to the cost matrix of subproblem 6. The optimal solution to
subproblem 6 is z = 704, x15 = x34 = x23 = x42 = x52 = 1. This solution
contains no subtours, but z-value > 668.

City 1 2 3 4 5
1 M 132 217 164 58
2 132 M 290 201 M
3 217 290 M 113 303
4 164 201 M M 196
5 58 79 303 196 M
Cost matrix of subproblem 6
SQQP3043 – Heuristic Techniques 29

Subproblem 1
z = 495
x15 = x21 = x34 =
x43 = x52 = 1
x34 = 0 x43 = 0

Subproblem 2 Subproblem 3
z = 652 z = 652
x14 = x25 = x31 = x13 = x25 = x34 =
x43 = x52 = 1 x41 = x52 = 1
x25 = 0 x52 = 0 UB = 668
x25 = 0 x52 = 0
Subproblem 4 Subproblem 5
z = 668 z = 704
x15 = x24 = x31 = x14 = x43 = x32 =
x43 = x52 = 1 x25 = x51 = 1
candidate sol. UB = 668

Subproblem 6 Subproblem 7
z = 704 z = 910
x15 = x34 = x23 = x13 = x25 = x31 =
x42 = x52 = 1 x42 = x54 = 1
UB = 668 UB = 668

• Solve subproblem 7 using Hungarian method to the cost matrix of

subproblem 7. The optimal solution to subproblem 6 is z = 910, x13 = x25
= x31 = x42 = x54 = 1. This solution contains no subtours, but z-value >
668.

City 1 2 4 3 5
1 M 132 217 164 58
2 132 M 290 201 79
3 217 290 M 113 303
4 164 201 M M 196
5 58 M 303 196 M
Cost matrix of subproblem 7