Branch and bound strategy.

135views

written 8.4 years ago by

teamques10 ★ 68k

Branch and bound is a systematic method for solving optimization problems
B&B is a rather general optimization technique that applies where the greedy method and dynamic programming fail.
However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case.
On the other hand, if applied carefully, it can lead to algorithms that run reasonably fast on average.
The general idea of B&B is a BFS-like search for the optimal solution, but not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion determines which node to expand and when, and another criterion tells the algorithm when an optimal solution has been found.
The General Branch and Bound Algorithm
Each solution is assumed to be expressible as an array X [1:n] (as was seen in Backtracking).
A predictor, called an approximate cost function CC, is assumed to have been defined.
Definitions:
- A live node is a node that has not been expanded
- A dead node is a node that has been expanded
- The expanded node (or E-node for short) is the live node with the best CC value

The general B&B algorithm follows:.

    Procedure DFBranchAndBound(G,s,goal,h,bound0) 
    Inputs:
            G: graph with nodes N and arcs A 
             s: start node 
             goal: Boolean function on nodes 
             h: heuristic function on nodes 
            bound0: initial depth bound (can be ∞ if not specified) 
    Output
             a least-cost path from s to a goal node if there is a solution with  cost less than bound0 or ⊥ if there is no solution with cost less than bound0 
    Local
             best_path: path or ⊥ 
             bound: non-negative real 
             Procedure cbsearch(⟨n0,...,nk⟩) 
                       if (cost(⟨n0,...,nk⟩)+h(nk) < bound) then 
                       if (goal(nk)) then 
                                 best_path ←⟨n0,...,nk⟩ 
                                 bound ←cost(⟨n0,...,nk⟩) 
                       else
                                 for each arc ⟨nk,n⟩∈A do 
                                          cbsearch(⟨n0,...,nk,n⟩) 
    best_path ←⊥ 
    bound ←bound0 
    cbsearch(⟨s⟩) 
    return best_path

The internal procedure cbsearch, for cost-bounded search, uses the global variables to provide information to the main procedure.
Initially, bound can be set to infinity, but it is often useful to set it to an overestimate, bound0, of the path cost of an optimal solution. This algorithm will return an optimal solution - a least-cost path from the start node to a goal node - if there is a solution with cost less than the initial bound bound0.
If the initial bound is slightly above the cost of a lowest-cost path, this algorithm can find an optimal path expanding no more arcs than A* search. This happens when the initial bound is such that the algorithm prunes any path that has a higher cost than a lowest-cost path; once it has found a path to the goal, it only explores paths whose the f-value is lower than the path found. These are exactly the paths that A* explores when it finds one solution.
If it returns ⊥ when bound0=∞, there are no solutions. If it returns ⊥ when bound0 is some finite value, it means no solution exists with cost less than bound0. This algorithm can be combined with iterative deepening to increase the bound until either a solution is found or it can be shown there is no solution.

ADD COMMENT EDIT