Branch and Bound Algorithms

Terminology
● Live node is a node that has been generated but whose
children have not yet been generated.
● E-node is a live node whose children are currently being
explored. In other words, an E-node is a node currently being
expanded.
● Dead node is a generated node that is not to be expanded or
explored any further. All children of a dead noden have
already been expanded.
● Branch-and-bound refers to all state space search methods in
which all children of an E-node are generated before any other
live node can become the E-node.
■ Used for state space search
■ In BFS, exploration of a new node cannot begin until the node
currently being explored is fully explored
 General method
● Both BFS and DFS generalize to branch-and-
bound strategies
■ BFS is an FIFO search in terms of live nodes
■ List of live nodes is a queue
● DFS is an LIFO search in terms of live nodes
■ List of live nodes is a stack
● Just like backtracking, we will use bounding
functions to avoid generating subtrees that do
not contain an answer node
 Example: 4-queens

● Backtracking is superior method for this search

problem 1
x1 = 1 x1=2
2 18
x2=2 3 4 x2=1 x2=3 x2 = 4
B 3 8 13 19 24 29
x3=3 x3=4 2 3 B B
4 6 14 16 x3 = 1
x4=4 3 B 30
5 7 15 x4 = 3
B 31
 Least Cost (LC) search
● Selection rule does not give preference to nodes that
will lead to answer quickly but just queues those
behind the current live nodes
■ In 4-queen problem, if three queens have been placed on
the board, it is obvious that the answer may be reached in
one more move
■ The rigid selection rule requires that other live nodes be
expanded and then, the current node be tested
● Rank the live nodes by using a heuristic ĉ(·)
 LC Search

● ĉ(x) = f(h(x)) + ĝ(x)

■ ĝ(x) is an estimate of the additional effort needed
to reach an answer from node x
■ h(x) is the cost of reaching x from root and f(·) is
any nondecreasing function
● Choose next E-node a live node with least ĉ
 15-puzzle problem
● 15 numbered tiles on a square frame with a capacity for 16
tiles. Given an initial arrangement, transform it to the goal
arrangement through a series of legal moves
● The state space of an initial state is all the states that can be
reached from initial state

1 3 4 15 1 2 3 4
2 5 12 5 6 7 8
7 6 11 14 9 10 11 12
8 9 10 13 13 14 15
Initial State Goal State
 LC Search on 15-puzzle problem
● Children of each node x represent the states reachable from x
in one legal move
● Consider the move as move of empty space rather than tile
● Empty space can have four legal moves: up, down, left, right
● One possible choice for ĝ(x) is the number of nonblank tiles
not in their goal position
 Bounding
● Each answer node x has a cost c(x) and we have to find a
minimum-cost answer node
● Use a cost function ĉ(x) such that ĉ(x) ≤ c(x) provides lower
bound on the solution obtainable from any node x
● If U is the upper bound on the cost of a minimum-cost
solution, then all live nodes x with ĉ(x) > U may be killed
■ All answer nodes reachable from x have cost c(x) ≥ ĉ(x) > U
■ Starting value for U can be obtained by some heuristic or set to ∞
■ Each time a new answer node is found, the value of U can be updated
● Optimization/minimization problem
■ Maximization converted to minimization by changing sign of objective
function
■ Formulate the search for an optimal solution as a search for a least-cost
answer node in a state space search tree
 TSP using LCBB
● Dynamic Programming Solution takes O(n22n ) time
● Worst case of BB O(n22n )
● Significant time improvement through use of good bounding
functions with Branch and Bound
● G = (V, E) represented through cost matrix C
● Assume every tour starts and ends at vertex 1
● Solution space is given by S = {1, π, 1 | π is a permutation of
(2,3,…,n)}
● |S| = (n-1)!
● Size can be reduced by restricting S so that (1, i1, i2, …,in-1, 1) Є
S iff (ij, ij+1) Є E
 TSP using LCBB
length of tour defined by the path from
● c(A) = the root to node A, if A is a leaf

cost of min-cost in the subtree A, if A is not

a leaf
● ĉ(A) = length of path defined at node A
≤ c(r) ≤ u(r) for all nodes r
● ĉ(r)
● Better ĉ(A) is obtained by reduced cost matrix
corresponding to G
■ A row(column) is said to be reduced iff it contains at least
one zero and all reaining entries are non-negative
 Example
∞ 20 30 10 11 ∞ 10 17 0 1
15 ∞ 16 4 2 12 ∞ 11 2 0
3 5 ∞ 2 4 0 3 ∞ 0 2
19 6 18 ∞ 3 15 3 12 ∞ 0
16 4 7 16 ∞ 11 0 0 12 ∞
Cost Matrix Reduced Cost Matrix
● RCM obtained by subtracting 10, 2, 2, 3, 4 from rows and 1
and 3 from columns 1 and 3.
● A minimum cost tour remains a minimum cost tour after this
operation.
● The total cost subtracted is the lower bound on the min cost
tour
● This value is used as ĉ (=25)
 TSP using LCBB
● Associate a RCM with every node
● Let A be the RCM for node R & let S be a child of R such
that tree edge (R,S) corresponds to including edge (i,j) in the
tour.
● If S is not a leaf then RCM for S can be obtained as follows
1. Change all entries in row i and column j to ∞. (Any edges leaving i or
entering j are not used)
2. A(j,1) = ∞ (edge (j,1) cannot be used again)
3. Reduce all rows and columns except those containing only ∞. B is the
resultant matrix
● If r is the total amount subtracted in step 3, then
ĉ(S) = ĉ(R) + A(i,j) + r
● Initialize upper to ∞. Update upper after getting the first
answer node. After that discard any nodes with ĉ > upper
 RCM for node 1
25
∞ 10 17 0 1
1
12 ∞ 11 2 0 (1,2)
0 3 ∞ 0 2
35 2
15 3 12 ∞ 0
11 0 0 12 ∞ RCM for node 2

∞ ∞ ∞ ∞ ∞
∞ ∞ 11 2 0 Ĉ(2) = Ĉ(1) + A(1,2) + r
=25 + 10 + 0 = 35
0 ∞ ∞ 0 2
15 ∞ 12 ∞ 0
11 ∞ 0 12 ∞
 RCM for node 1

∞ 10 17 0 1 25
1
12 ∞ 11 2 0 (1,2)
(1,3)
0 3 ∞ 0 2
15 3 12 ∞ 0 35 2 3 53

11 0 0 12 ∞ RCM for node 3

∞ ∞ ∞ ∞ ∞
1 ∞ ∞ 2 0 Ĉ(3) = Ĉ(1) + A(1,3) + r
=25 + 17 + 11 = 53
∞ 3 ∞ 0 2
4 3 ∞ ∞ 0
0 0 ∞ 12 ∞
 RCM for node 1

∞ 10 17 0 1 25
1
12 ∞ 11 2 0 (1,2)
(1,3) (1,4)
0 3 ∞ 0 2
15 3 12 ∞ 0 35 2 3 53 4 25

11 0 0 12 ∞ RCM for node 4

∞ ∞ ∞ ∞ ∞
12 ∞ 11 ∞ 0 Ĉ(4) = Ĉ(1) + A(1,4) + r
=25 + 0 + 0 = 25
0 3 ∞ ∞ 2
∞ 3 12 ∞ 0
11 0 0 ∞ ∞
 RCM for node 1

∞ 10 17 0 1 25
1
12 ∞ 11 2 0 (1,2) (1,5)

0 3 ∞ 0 2 35 2 (1,3) (1,4)
5 31
3
15 3 12 ∞ 0 53
4 25
11 0 0 12 ∞ RCM for node 5

∞ ∞ ∞ ∞ ∞
10 ∞ 9 0 ∞ Ĉ(5) = Ĉ(1) + A(1,5) + r
=25 + 1 + 5 = 31
0 3 ∞ 0 ∞
12 0 9 ∞ ∞
∞ 0 0 12 ∞
 Node 4 becomes the next E-node
25
1
RCM for node 4 (1,2) (1,5)

∞ ∞ ∞ ∞ ∞ 35 2 (1,3) (1,4)
5 31
3
12 ∞ 11 ∞ 0 53
4 25
0 3 ∞ ∞ 2 (4,2)

∞ 3 12 ∞ 0 6
11 0 0 ∞ ∞ RCM for node 6 28

∞ ∞ ∞ ∞ ∞
∞ ∞ 11 ∞ 0 Ĉ(6) = Ĉ(4) + A(4,2) + r
=25 + 3 + 0 = 28
0 ∞ ∞ ∞ 2
∞ ∞ ∞ ∞ ∞
11 ∞ 0 ∞ ∞
 25
1
RCM for node 4 (1,2) (1,5)

∞ ∞ ∞ ∞ ∞ 35 2 (1,3) (1,4)
5 31
3
12 ∞ 11 ∞ 0 53
4 25
0 3 ∞ ∞ 2 (4,2)
(4,3)
∞ 3 12 ∞ 0 6
7 50
11 0 0 ∞ ∞ RCM for node 7 28

∞ ∞ ∞ ∞ ∞
1 ∞ ∞ ∞ 0 Ĉ(7) = Ĉ(4) + A(4,3) + r
=25 + 12 + 13 = 50
∞ 1 ∞ ∞ 0
∞ ∞ ∞ ∞ ∞
0 0 ∞ ∞ ∞
 25
1
RCM for node 4 (1,2) (1,5)

∞ ∞ ∞ ∞ ∞ 35 2 (1,3) (1,4)
5 31
3
12 ∞ 11 ∞ 0 53
4 25
(4,5)
0 3 ∞ ∞ 2 (4,2)
(4,3)
∞ 3 12 ∞ 0 6
8
7 50 36
11 0 0 ∞ ∞ RCM for node 8 28

∞ ∞ ∞ ∞ ∞
1 ∞ 0 ∞ ∞ Ĉ(8) = Ĉ(4) + A(4,5) + r
=25 + 0 + 11 = 36
0 3 ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ 0 0 ∞ ∞
 Node 6 becomes the next E-node
25
1
RCM for node 6 (1,2) (1,5)

∞ ∞ ∞ ∞ ∞ 35 2 (1,3) (1,4)
5 31
3
∞ ∞ 11 ∞ 0 53
4 25
(4,5)
0 ∞ ∞ ∞ 2 (4,2)
(4,3)
∞ ∞ ∞ ∞ ∞ 28 6
8
7 50 36
11 ∞ 0 ∞ ∞ RCM for node 9 (2,3)

∞ ∞ ∞ ∞ ∞ 9 52
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ 0 Ĉ(9) = Ĉ(6) + A(2,3) + r
∞ ∞ ∞ ∞ ∞ =28+ 11 + 13 = 52

0 ∞ ∞ ∞ ∞
 25
1
RCM for node 6 (1,2) (1,5)

∞ ∞ ∞ ∞ ∞ 35 2 (1,3) (1,4)
5 31
3
∞ ∞ 11 ∞ 0 53
4 25
(4,5)
0 ∞ ∞ ∞ 2 (4,2)
(4,3)
∞ ∞ ∞ ∞ ∞ 28 6
8
7 50 36
11 ∞ 0 ∞ ∞ RCM for node 10 (2,3)
(2,5)
∞ ∞ ∞ ∞ ∞ 9 52
10 28
∞ ∞ ∞ ∞ ∞
0 ∞ ∞ ∞ ∞ Ĉ(10) = Ĉ(6) + A(2,5) + r
∞ ∞ ∞ ∞ ∞ =28+ 0 + 0 = 28

∞ ∞ 0 ∞ ∞
 Node 10 becomes the next E-node
25

RCM for node 11 1

(1,2) (1,5)

∞ ∞ ∞ ∞ ∞ 35 2 (1,3) (1,4)
5 31
3
∞ ∞ ∞ ∞ ∞ 53
4 25
(4,5)
∞ ∞ ∞ ∞ ∞ (4,2)
(4,3)
∞ ∞ ∞ ∞ ∞ 28 6
8
36
∞ ∞ 0 ∞ ∞ (2,3) (2,5) 7 50

10 28
9 52
(5,3)
11 is the solution node - path 1,4,2,5,3,1
upper = 28 11 28
For the next E-node 5 Ĉ(5) = 31 > upper Ĉ(11) = Ĉ(10) + A(5,3) + r
Hence, LCBB terminates =28+ 0 + 0 = 28