Branch and Bound

Branch and Bound Method

• Branch and bound is a systematic method for solving
optimization problems.
• It is a state space search method in which all the children of
a node are generated before expanding any of its children.
• It is a BFS-like search for the optimal solution.
• After generating nodes at a level, we take the decision for
expanding a node based on some criterion.
• It is much slower. Indeed, it often leads to exponential time
complexity in the worst case.
 Travelling Salesman Problem
• The travelling salesman problem (TSP) is as follows:
• Given a list of cities and a table of distances from each city
to the others. A salesman has to visit every city exactly
once. He has to come back to the city from where he starts
his journey. Find the shortest possible route that the
salesman must follow to complete his tour.
• If there are n nodes, there are (n-1)! feasible solutions.
From these feasible solutions we have to find optimal
solution.
Example
 Row Reduced Column
matrix Reduced matrix

• 4+5+6+2+1=18 that is the cost associated with

node n1(A).
 Path A->B
• C[A,B] = 0
• Set row-A and column-B to ∞
• C[B,A]= ∞

Row Reduced Column

matrix Reduced matrix

Cost of node n2(B)

= C[A,B]+C[n1] +
reduction
= 0 + 18 + 18 = 36
 Path A → C
• C[A,C] = 7
• Set row-A and column-C to ∞
• Set C[C,A] = ∞

It is already
reduced matrix.
Cost of node n3(C)
= C[A,C]+C[n1] +
reduction
= 7 + 18 + 0 = 25
 Path A → D
• C[A,D] = 3
• Set row-A and column-D to ∞
• Set C[D,A] = ∞

Row Reduced
matrix
It is already column
reduced matrix.
Cost of node n4(D)
= C[A,D]+C[n1] +
reduction
= 3 + 18 + 5 = 26
• Cost(n2) = 36 (for Path A → B)
• Cost(n3) = 25 (for Path A → C)
• Cost(n4) = 26 (for Path A → D)
• The node with the lowest cost is selected to extend further.
• Now sales person can visit city B and city D from city C.

Cost Matrix at
node n3(C)
 Path A → C → B
• select value of C[C,B] from matrix i.e. C[C,B] = ∞
• Set row-C and column-B to ∞
• Set C[B,A] = ∞

It is already column
reduced matrix.
Cost of node n5(B)
= C[C,B]+C[n3] +
reduction
= ∞ + 25 + (13 + 8)
=∞
 Path A → C → D
• C[C,D] = 0
• Set row-C and column-D to ∞
• Set C[D,A] = ∞

• It is already reduced matrix .

• Cost of node n6(D) = C[C,D] + C[n3] + reduction
• = 0 + 25 + 0 = 25
 Path A → C → D → B
• Now we prefer to expand node n6(D). Sales person can visit city B
from city D.

• C[D,B] = 0
• Set row-D and column-B to ∞
• Set C[B,A] = ∞
• Cost of node n7(B) = C[D,B] + cost(n6)
+ reduction
= 0 + 25 +0 =25
 Optimal Solution
• Thus the optimal path is A-> C -> D -> B -> A
• Cost is 12 + 6 + 2 + 5 = 25
 Travelling Salesman Problem
• Example – undirected graph

1 2 3 4 5
1 inf 10 8 9 7
2 10 inf 10 5 6
3 8 10 inf 8 9
4 9 5 8 inf 6
5 7 6 9 6 inf
 Step1
• Reduce the initial distance or cost matrix by performing row
reduction and column reduction.

1 2 3 4 5
1 inf 10 8 9 7
2 10 inf 10 5 6
3 8 10 inf 8 9
4 9 5 8 inf 6
5 7 6 9 6 inf
• Row reduced matrix

1 2 3 4 5
1 inf 3 1 2 0
2 5 inf 5 0 1
3 0 2 inf 0 1
4 4 0 3 inf 1
5 1 0 3 0 inf
• Column reduced matrix

1 2 3 4 5 1 2 3 4 5
1 inf 3 1 2 0 1 inf 3 0 2 0
2 5 inf 5 0 1 2 5 inf 4 0 1
3 0 2 inf 0 1 3 0 2 inf 0 1
4 4 0 3 inf 1 4 4 0 2 inf 1
5 1 0 3 0 inf 5 1 0 2 0 inf

• This is the completely reduced matrix of initial distance matrix.

• Thus the distance or cost associated with node n1 (city 1) is sum of
all reduction elements. i.e 7 + 5 + 8 + 5 + 6 + 1 = 32.
• We create a node n1 that represent city 1. It is the root node.
1 n1(32)

• From city 1 , sales person can visit city 2, city 3, city 4, city 5.
• Node n1 can have 4 children. For every node we will find out
cost associated with each node.
1 n1(32)

2 n2(36) 3 n3(34) 4 n4(37) 5 n5(34)

 Step 2
• Calculate cost associated with other nodes:
• For node n2,
– c(1,2) = 3
– make all the values in row 1 and column 2 as infinite.
– Sales man can’t go back from city 2 to city 1. Thus c(2,1) = inf.

1 2 3 4 5
1 inf inf inf inf inf
2 inf inf 4 0 1
3 0 inf inf 0 1
4 4 inf 2 inf 1 1
5 1 inf 2 0 inf
• Perform row reduction and column reduction
Matrix N2
1 2 3 4 5 1 2 3 4 5
1 inf inf inf inf inf 1 inf inf inf inf inf
2 inf inf 4 0 1 2 inf inf 3 0 1
3 0 inf inf 0 1 3 0 inf Inf 0 1
4 3 inf 1 inf 0 4 3 inf 0 inf 0
5 1 inf 2 0 inf 5 1 inf 1 0 inf

1
• Cost associated with node n2 = c(n2) = c(1,2) + c(n1) + reduction
• = 3 + 32 + 2= 36
• Cost associated with n3 i.e c(n3) = 34
Matrix N3
1 2 3 4 5
1 inf inf inf inf inf
2 4 inf inf 0 0
3 inf 2 inf 0 0
4 3 0 inf inf 0
5 0 0 inf 0 inf
• Cost associated with n4 i.e c(n4) = 37
Matrix N4
1 2 3 4 5
1 inf inf inf inf inf
2 4 inf 1 inf 0
3 0 2 inf inf 1
4 4 0 0 inf 1
5 1 0 0 inf inf
• Cost associated with n5 i.e c(n5) = 34
Matrix N5
1 2 3 4 5
1 inf inf inf inf inf
2 5 inf 2 0 inf
3 0 2 inf 0 inf
4 4 0 0 inf inf
5 1 0 0 0 inf

• Node n3 and n5 both have the same value. This value is

minimum. We can expand either n3 or n5.
• Suppose we expand node n5 using step 2.
• Sales person can visit from node n5 to node n6 (2), node n7
(3), and node n8 (4).
• Cost associated with n6 i.e c(n6) = c(5,2) + c(5) + reduction=
0+34+0=34
• C(5,2) =0
• In matrix N5, make row 5 and column 2 as infinite. C(2,1) =inf.
Reduce that matrix.
Matrix N5 Matrix N6

1 2 3 4 5 1 2 3 4 5
1 Inf inf inf inf Inf 1 inf inf inf inf inf
2 5 inf 2 0 Inf 2 inf inf 2 0 inf
3 0 2 inf 0 inf 3 0 inf inf 0 inf
4 4 0 0 inf inf 4 4 inf 0 inf inf
5 1 0 0 0 inf 5 inf inf inf inf inf
• Cost associated with n7 i.e c(n7) = c(5,3) + c(5) + reduction=
0+34+4=38
Matrix N7
1 2 3 4 5
1 inf inf inf inf inf
2 1 inf inf 0 inf
3 inf 2 inf 0 inf
4 0 0 inf inf inf
5 inf inf inf inf inf
• Cost associated with n8 i.e c(n8) = c(5,4) + c(5) + reduction=
0+34+2=36
Matrix N8

1 2 3 4 5
1 Inf inf inf inf Inf
2 3 inf 0 inf Inf
3 0 2 inf inf inf
4 inf 0 0 inf inf
5 inf inf inf inf inf

• Choose node with minimum value. Now again we have two

nodes n3 and node n6.
• Now suppose we expand node n3. use matrix N3 and repeat
similar procedure.
Matrix N3
1 2 3 4 5
1 inf inf inf inf inf
2 4 inf inf 0 0
3 inf 2 inf 0 0
4 3 0 inf inf 0
5 0 0 inf 0 inf
• Create node n9(2), node n10(4) and node n11(5). Compute
cost associated with these nodes.
• Now we can expand nodes n6, n10, and n11.

• The optimal solution will be 1-3-4-2-5-1. Cost of solution is 8 +

8 + 5 + 6 + 7 = 34.
 Assignment
• Solve 0/1 knapsack using branch and bound
method.
• Solve TSP using greedy approach.
• Write algorithm to solve TSP using branch and
bound with the use of min heap and graph
data structure.