Home Algorithm

# Branch and Bound

  • The branch-and-bound algorithm developed here is an improvement on the backtracking algorithm.
  • The B&B design strategy is very similar to backtracking in that a state space tree is used to solve a problem.
  • B&B vs. Backtracking
    • B&B does not limit us to any particular way of traversing the tree and
    • B&B is used only for optimization problems
  • A B&B algorithm computes a number (bound) at a node to determine whether the node is promising.
    • If that bound is no better than the value of the best solution found so far, the node is nonpromising.
    • Otherwise, it is promising.

# 0-1 Knapsack Example

# Best-First Search with Branch-and-Bound Pruning

  • In general, the breadth-first search strategy has no advantage over a DFS (backtracking).
  • However, we can improve our search by using our bound to do more than just determine whether a node is promising.
  • After visiting all the children of a given node, we can look at all the promising, unexpanded nodes and expand beyond the one with the best bound.
  • In this way, we often arrive at an optimal solution more quickly than if we simply proceeded blindly in a predetemined order.

  1. Visit node (0, 0) (the root)
    • Compute its profit = $0 , weight = 0 , bound = $115 .
    • Set maxprofit = 0 .
  2. Visit node (1, 1)
    • Compute its profit = $40 , weight = 2 , bound = $115 .
    • Because weight = 2 < W = 16 and profit = $40 > maxprofit = $0 set maxprofit = $40 .
  3. Visit node (1, 2)
    • Compute its profit = $0 , weight = 0 , bound = $82 .
    • maxprofit = $40 .

Determine promising, unexpanded node with the greatest bound.

  • Because node (1, 1) has a bound of $115 and node (1, 2) has a bound of $82, node (1, 1) is the promising, unexpanded node with the grearest bound.
  • We visit its children next.
  1. Visit node (2, 1)
    • Compute its profit = $70 , weight = 7 , bound = $115 .
    • Because weight = 7 < W = 16 and profit = $70 > maxprofit = $40 set maxprofit = $70 .
  2. Visit node (2, 2)
    • Compute its profit = $40 , weight = 2 , bound = $98 .
    • maxprofit = $70 .

Determine promising, unexpanded node with the greatest bound.

  • That node is node (2, 1). We visit its children next.
  1. Visit node (3, 1)
    • Compute profit = $120 , weight = 17 .
    • It is nonpromising because its weight = 17 > W = 16 , set bound = 0
  2. Visit node (3, 2)
    • Compute profit = $70 , weight = 7 , bound = $80 .
    • maxprofit = $70 .

Determine promising, unexpanded node with the greatest bound.

  • That node is node (2, 2). We visit its children next.
  1. Visit node (3, 3)
    • Compute its profit = $90 , weight = 12 , bound = $98 .
    • Because weight = 12 < W = 16 and profit = $90 > maxprofit = $70 , set maxprofit = $90 .
    • At this point, nodes (1, 2) and (3, 2) become nonpromising because their bound , $82 and $80 are less than $90 = maxprofit .
  2. Visit node (3, 4)
    • Compute its profit = $40 , weight = 2 , bound = $50 .
    • It is nonpromising because its bound = $50 < $90 = maxprofit .

Determine promising, unexpanded node with the greatest bound.

  • That node is node (3, 3). We visit its children next.
  1. Visit node (4, 1)
    - Compute its profit = $100 , weight = 17 => nonpromising.
  2. Visit node (4, 2)
    - Compute its profit = $90 , weight = 12 , bound = $90 => nonpromising.

Because there are now no promising, unexpanded nodes, we are done.

# Traveling Salesperson Problem

Find the shortest path in a directed graph that starts at a given vertex, visits each vertex exactly once, and ends up back at the starting vertex.

Such a tour is called an optimal tour.

# B&B Approach

  • A lower bound should be determined on the length of any tour that can be obtained by expanding beyond a given node. (In 0-1 Knapsack problem, we need an upper bound.)
  • A node is promising only if its bound < current minimum tour length .
  • In any tour, the length of the edge taken when leaving a vertex must be at least as great as the length of the shortest edge emanating from that vertex.
  • If the graph of a TSP is represented by Adjacency Matrix, then the lower bound on the cost of leaving vertex vi is the minimum of all the nonzero entries in row i.

  • Because a tour must leave every vertex exactly once, a lower bound on the length of a tour is the sum of these minimums.
  • Therefore, a lower bound on the length of a tour is 4 + 7 + 4 + 2 + 4 = 21 .
  • This is not to say that there is a tour with this length. Rather, it says that there can be no tour with a shorter length.

If we have visited the node containing [1, 2], then the cost of getting from v1 to v2 is the weight on the edge from v1 to v2 (14), and any tour obtained by expanding beyond v2 has the following lower bounds.

  • For v1: lower bound is determined.
  • For v2: edge to v1 should not be included.
  • For other vertices: edge to v2 is not included.

Now, a lower bound on the length of a tour is 14 + 7 + 4 + 2 + 4 = 31