fdocuments.in_branch-and-bound-design-and-analysis-of-alogorithm.ppt

Branch & Bound Algorithms
Briana B. Morrison
With thanks to Dr. Hung

2
Topics
 Define branch & bound
 0-1 Knapsack problem
– Breadth-First Search
– Best-First Search
 Assignment Problem
 Traveling Salesperson

3
Introduction
 The branch-and-bound design strategy is very similar to
backtracking in that a state space tree is used to solve a
problem.
 The differences are that the branch-and-bound method
1) does not limit us to any particular way of traversing
the tree, and 2) is used only for optimization problems.
 A branch-and-bound algorithm computes a number
(bound) at a node to determine whether the node is
promising.

4
Introduction …
 The number is a bound on the value of the solution
that could be obtained by expanding beyond the
node.
 If that bound is no better than the value of the best
solution found so far, the node is nonpromising.
Otherwise, it is promising.
 The backtracking algorithm for the 0-1 Knapsack
problem is actually a branch-and-bound algorithm.
 A backtracking algorithm, however, does not exploit
the real advantage of using branch-and-bound.

5
Introduction …
 Besides using the bound to determine whether a
node is promising, we can compare the bounds of
promising nodes and visit the children of the one
with the best bound.
 This approach is called best-first search with
branch-and-bound pruning. The implementation of
this approach is a modification of the breadth-first
search with branch-and-bound pruning.

6
Branch and Bound
 An enhancement of backtracking
 Applicable to optimization problems
 Uses a lower bound for the value of the
objective function for each node (partial
solution) so as to:
– guide the search through state-space
– rule out certain branches as
“unpromising”

7
0-1 Knapsack
 To learn about branch-and-bound, first we look at
breadth-first search using the knapsack problem
 Then we will improve it by using best-first search.
 Remember the default strategy for the 0-1 knapsack
problem was to use a depth-first strategy, not
expanding nodes that were not an improvement on
the previously found solution.

8
BackTracking (depth-first)
8
17 10 8
14 11
13
12
20
17

9
Breadth-first Search
 We can implement this search using a queue.
 All child nodes are placed in the queue for later
processing if they are promising.
 Calculate an integer value for each node that
represents the maximum possible profit if we pick
that node.
 If the maximum possible profit is not greater than
the best total so far, don’t expand the branch.

10
Breadth-first Search
 The breadth-first search strategy has no advantage
over a depth-first search (backtracking).
 However, we can improve our search by using our
bound to do more than just determine whether a
node is promising.

11
Branch and Bound (breadth-first)
8
17 10 8
14 11
13
12
20
17

12
0-1 Knapsack
 0-1 Knapsack using the branch and bound.
 Now look at all promising, unexpanded nodes and
expand beyond the one with the best bound.
 We often arrive at an optimal solution more quickly
than if we simply proceeded blindly in a
predetermined order.

13
Best-first Search
 Best-first search expands the node with the
best bounds next.
 How would you implement a best-first search?
– Depth-first is a stack
– Breadth-first is a queue
– Best-first is a ???

14
Branch and Bound (best first)
8
17 10 8
14 11
13
12
20
17

15
0-1 Knapsack
 Capacity W is 10
 Upper bound is $100 (use fractional value)
Item Weight Value Value / weight
1 4 $40 10
2 7 $42 6
3 5 $25 5
4 3 $12 4

16
Computing Upper Bound
 To compute the upper bound, use
– ub = v + (W – w)(vi+1/wi+1)
 So the maximum upper bound is
– pick no items, take maximum profit item
– ub = (10 – 0)*($10) = $100
 After we pick item 1, we calculate the upper bound as
– all of item 1 (4, $40) + partial of item 2 (7, $42)
– $40 + (10-4)*6 = $76
 If we don’t pick item 1:
– ub = (10 – 0) * ($6) = $60

17
State Space Tree
w = 0, v = 0
ub = 100
w = 4, v = 40
ub = 76 w = 0, v = 0
ub = 60
w = 11 w = 4, v = 40
ub = 70
w = 9, v = 65
ub = 69 w = 4, v = 40
ub = 64
w = 12 w = 9, v = 65
ub = 65
0
1
3
2
4
with 1 without 1
with 2 without 2
without 3
with 3
with 4 without 4
5
6
7 8
inferior to
node 8
not feasible
not feasible
inferior to
node 8
optimal solution

18
Bounding
 A bound on a node is a guarantee that any solution
obtained from expanding the node will be:
– Greater than some number (lower bound)
– Or less than some number (upper bound)
 If we are looking for a maximal optimal (knapsack),
then we need an upper bound
– For example, if the best solution we have found so far has a
profit of 12 and the upper bound on a node is 10 then there
is no point in expanding the node
 The node cannot lead to anything better than a 10

19
Bounding
 Recall that we could either perform a depth-first or a
breadth-first search
– Without bounding, it didn’t matter which one we used
because we had to expand the entire tree to find the optimal
solution
– Does it matter with bounding?
 Hint: think about when you can prune via bounding

20
Bounding
 We prune (via bounding) when:
(currentBestSolutionCost >= nodeBound)
 This tells us that we get more pruning if:
– The currentBestSolution is high
– And the nodeBound is low
 So we want to find a high solution quickly and we want
the highest possible upper bound
– One has to factor in the extra computation cost of computing
higher upper bounds vs. the expected pruning savings

21
Enumeration in a search tree
 each node is a partial solution, i.e. a part of the solution
space
...
...
root node
child nodes
child nodes
Level 0
Level 1
Level 2

22
The assignment problem
 We want to assign n people to n jobs so that
the total cost of the assignment is as small as
possible (lower bound)

23
Select one element in each row of the cost matrix C so that:
• no two selected elements are in the same column; and
• the sum is minimized
For example:
Job 1 Job 2 Job 3 Job 4
Person a 9 2 7 8
Person b 6 4 3 7
Person c 5 8 1 8
Person d 7 6 9 4
Lower bound: Any solution to this problem will have
total cost of at least:
Example: The assignment problem
sum of the smallest element in each row =
10

24
Assignment problem: lower bounds

27
Traveling Salesman Problem
 Can apply branch & bound if we come up with a
reasonable lower bound on tour lengths.
 Simple lower bound = finding smallest element in the
intercity distance matrix D and multiplying it by
number of cities n
 Alternate solution:
– For each city i, find the sum si of the distances from city i to
the two nearest cities;
– compute the sum s of these n numbers;
– divide the result by 2
– and if all the distances are integers, round up the result to
the nearest integer;

28
Traveling salesman
example:
lb = [(1+3)+(3+6)+(1+2)+(3+4)+(2+3)]/2 = 14

29
Summary: Branch and bound
– Feasible solution
– Optimal solution
– Breadth-First Search
– Best-First Search (with branch-and-bound pruning)

30
 Branch and Bound is:
– a general search method.
– minimize a function f(x), where x is restricted to some
feasible region.
 To apply branch and bound, one must have:
– a means of computing a lower bound on an instance of the
optimization problem.
– a means of dividing the feasible region of a problem to
create smaller subproblems.
– a way to compute an upper bound (feasible solution) for at
least some instances.

31
 The method starts by:
– considering the original problem with the complete feasible
region (called the root problem).
– The lower-bounding and upper-bounding procedures are
applied to the root problem.
– If the bounds match, then an optimal solution has been found.
Otherwise, the feasible region is divided into two or more
regions, which together cover the whole feasible region.
– These subproblems become children of the root search node.
– The algorithm is applied recursively to the subproblems,
generating a tree of subproblems.

32
 If an optimal solution is found to a subproblem,
– it is a feasible solution to the full problem, but not
necessarily globally optimal.
– Since it is feasible, it can be used to prune the rest of the
tree:
 if the lower bound for a node exceeds the best known feasible
solution, no globally optimal solution can exist in the subspace
of the feasible region represented by the node.
 Therefore, the node can be removed from consideration.
– The search proceeds until all nodes have been solved or
pruned, or until some specified threshold is meet between
the best solution found and the lower bounds on all unsolved
subproblems.

fdocuments.in_branch-and-bound-design-and-analysis-of-alogorithm.ppt

Recommended

More Related Content

What's hot (20)

Similar to fdocuments.in_branch-and-bound-design-and-analysis-of-alogorithm.ppt (20)

Recently uploaded (20)

fdocuments.in_branch-and-bound-design-and-analysis-of-alogorithm.ppt