Branch and Bound
The branch and bound algorithm is similar to backtracking but is used for optimization problems. It performs a
graph transversal on the space-state tree, but general searches BFS instead of DFS.
During the search bounds for the objective function on the partial solution are determined. At each level the
best bound is explored first, the technique is called best bound first. If a complete solution is found then that
value of the objective function can be used to prune partial solutions that exceed the bounds.
The difficult of designing branch and bound algorithm is finding good bounding function. The bounding the
function should be inexpensive to calculate but should be effective at selecting the most promising partial
solution.
It works for minimization problem.
Lets consider a job sequencing problem as follows:
Job = {J1, J2, J3, J4}
P = {10, 5, 8, 3}
D = {1, 2, 1, 2}
Here, P is the penalty for not executing the job. We need to select the jobs in a sequence such that they complete
within the deadline with minimum penalty.
Lets see how to generate the state space tree for this problem.
In backtracking, the tree grows depth wise, but in branch and bound the tree grows level wise. Therefore, this
method uses breadth first search (BFS).
1
FIFO (Queue) Method J4
J1
J2 J3
2 3 4 5
J2 J4 J4
J3 J4
J3
6 7 8 9 10 11
J3 J4 J4 J4
12 13 14 15
J4
16
LIFO (Stack) Method 1
J4
J1
J2 J3
2 3 4 5
Put start node I in a stack
Since 1 is the only element at level 0, now 1 will be popped out from the stack and will be expanded next.
Push all children of 1 in stack. So 2, 3, 4, and 5 will be pushed into the stack.
Remove node 5 and expand it in the tree. However node 5 cannot be expanded further. So pop the next node.
1
J4
J1
J2 J3
2 3 4 5
J4
Pop 4 and push its child 6 in the stack.
6
Now pop 6 and explore. But it cannot be extended further. So pop the next one i.e. 3.
Push children of 3 into the stack.
1
J4
J1
J2 J3
2 3 4 5
J4 J4
J3
Push 7 and 8 in the stack.
7 8 6
Now pop 8 from the stack and explore it. Not
possible. So remove 7 and explore.
1
J4
J1
J2 J3
2 3 4 5
J4 J4
J3
7 8 6
J4
9
1
J4
J1
J2 J3
2 3 4 5
J2 J4 J4
J3 J4 J3
10 7 8 6
11 12
J4
2 is popped and explored.
1
J4
J1
J2 J3
2 3 4 5
J2 J4 J4
J3 J4 J3
10 7 8 6
11 12
J4
J4
9
13
1
J4
J1
J2 J3
2 3 4 5
J2 J4 J4
J3 J4 J3
10 7 8 6
11 12
J4
J4
9
13
1
J4
J1
J2 J3
2 3 4 5
J2 J4 J4
J3 J4 J3
10 7 8 6
11 12
J3 J4 J4
J4
14 15 9
13
1
J4
J1
J2 J3
2 3 4 5
J2 J4 J4
J3 J4 J3
10 7 8 6
11 12
J3 J4 J4
J4
14 15 9
13
This is known as LIFO method
J4
16
Least Cost Method
In this method, we will keep one measure at each 1 C=∞
node, i.e. cost.
J4
We will always explore the node with minimum J1
J2 J3
cost, i.e. node 3 (cost = 18)
C = 20 C = 18
C = 22 C = 25
2 3 4 5
Now again we will compute the costs at both nodes and explore them.
1 C=∞
J4
J1
J2 J3
C = 20 C = 18
C = 22 C = 25
2 3 4 5
J4
J3
C=8 6 7 C=4
Job Sequencing Problem
For solving the problem, we will have to take two
measures, cost and upper bound as follows: Jobs 1 2 3 4
Penalty 5 10 6 3
Upper bound(U) = sum of all the penalties except those
already included in the solution. Deadline 1 3 3 1
Time 1 2 1 1
Cost (C) = sum of all the penalties till the last job
considered.
Consider S is the set of jobs included in the solution then If we will not execute the job we will
have to pay the penalty.
U=∞
C=0 Upper = ∞
Step - 1
1
Jobs 1 2 3 4
J1
Penalty 5 10 6 3
U = 10+6+3 = 19 2 Upper = 19 Deadline 1 3 3 1
C=0
Time 1 2 1 1
U=∞
Step - 2 C=0
1
J1 Upper = 14
J2
U = 10+6+3 = 19 2
C=0 3 Smaller value will replace the large one.
U = 5+6+3 = 14 Cost should always be less than the
C=5 upper bound at any stage, otherwise kill
the node.
U=∞
Step - 3 C=0
1
Here cost is exceeding
J1 the upper bound. Kill the
J2 J3 node
U = 10+6+3 = 19 2
3 4 U = 5+10+3 = 18
C=0
C = 10+5 = 15
U = 5+6+3 = 14
C=5
Jobs 1 2 3 4
Penalty 5 10 6 3
Deadline 1 3 3 1
Time 1 2 1 1
U=∞
C=0
Upper = 14
1
J1 J4
J2 J3
U = 10+6+3 = 19 2 C = 10+5+6 = 21
C=0 3 4 5
Again greater
U = 5+6+3 = 14 U = 5+6+3 = 14 than upper
C=5 C = 10+5 = 15 bound.
Now we have only two live nodes. 2 and 3. Jobs 1 2 3 4
Penalty 5 10 6 3
Deadline 1 3 3 1
Time 1 2 1 1
U=∞
C=0
Upper = 9
1
J1 J4
J2 J3
C = 10+5+6
U = 10+6+3 = 19 3 4 5
C=0 2 U = 5+6+3 = 14 U = 5+6+3 = 14
C=5 C = 10+5
J2
J3 J4
Jobs 1 2 3 4
U = 6+3 = 9 6
C=0 7 8 Penalty 5 10 6 3
C = 10 C = 16 Deadline 1 3 3 1
Upper = 9 Time 1 2 1 1
Jobs 1 2 3 4
U=∞ Penalty 5 10 6 3
C=0
Deadline 1 3 3 1
1
Time 1 2 1 1
J1 J4
J2 J3
C = 10+5+6
U = 10+6+3 = 19 3 4 5
C=0 Upper = 8
2 U = 14 U = 14
C=5 C = 10+5
J2 J3 J4
J3 J4
U = 6+3 = 9 6 10
7 8 9
C=0
C = 16 C=5 C = 5+6
C = 10
U = 5+3 = 11
Upper = 9
=8
U=∞ Jobs 1 2 3 4
C=0
Penalty 5 10 6 3
1
Deadline 1 3 3 1
J1 J4
Time 1 2 1 1
J2 J3
U = 10+6+3 = 19 3 4 5
C=0 2 U = 14 U = 14
C=5 C = 10+5
J2 J3 J4 The next node to explore is
J3 J4 node 6, however, we can do a
check here that if job 1 and
U = 6+3 = 9 6 job 2 are executed, the total
9 10
C=0 7 8 time taken will be 3 unit. But
C=5 C = 5+6 now we cannot execute job 3
C = 10 C = 16
U = 5+3 = 11 as the deadline is 3.
Upper = 9
=8
Jobs 1 2 3 4
U=∞ Penalty 5 10 6 3
C=0
Deadline 1 3 3 1
1
Time 1 2 1 1
J1 J4
J2 J3
U = 10+6+3 = 19 3 4 5
C=0 2 U = 14 U = 14
C=5 C = 10+5
J2 J3 J4
J3 J4
U = 6+3 = 9 6 10
7 8 9
C=0
Fourth job also has the same case.
C = 16 C=5 C = 5+6
C = 10 So don't go for job 4.
U = 5+3 = 11
Upper = 8
=8
Jobs 1 2 3 4
U=∞ Now the last live node is 9. Expand this.
Penalty 5 10 6 3 C=0
Deadline 1 3 3 1 1 However, while checking the condition we
came to know that it cannot be expanded.
Time 1 2 1 1 J4
J1
J2 J3
U = 10+6+3 = 19 3 4 5 We have explored all the
C=0 nodes. Now check where we
2 U = 14 U = 14 are getting min cost and
C=5 C = 10+5
J2 J3 J4 upper bound.
J3 J4
U = 6+3 = 9 6 10
7 8 9
C=0
C = 16 C=5 C = 5+6
C = 10
U=8 = 11
Here we are getting min cost.
The optimal solution is {J2, J3}. We will be getting the total cost as 5
and the penalty for not executing J1 and J4 will be (3+5 = 8).
