Backtrack and Branch-and-Bound

From View

Jump to: navigation, search
Branch-and-bound tree structure.
Enlarge
Branch-and-bound tree structure.

Contents

Description

Branch and bound algorithms are effective for solving various search and global optimization problems. The goal in such problems is to search a very large space to find a globally optimal solution. Since the search space is intractably large, some implicit method is required in order to rule out regions of the search space that contain no interesting solutions. Branch and bound algorithms work by the divide and conquer principle: the search space is subdivided into smaller subregions (this subdivision is referred to as branching), and bounds are found on all the solutions contained in each subregion under consideration. The strength of the branch and bound approach comes when bounds on a large subregion show that it contains only inferior solutions, and so the entire subregion can be discarded without further examination.

Solution to a traveling salesman problem generated by a parallel branch-and-bound solver.
Enlarge
Solution to a traveling salesman problem generated by a parallel branch-and-bound solver.

Many fundamental problems can be solved with a branch and bound algorithm, such as Integer Linear Programming, Boolean Satisfiability, and Combinatorial Optimization problems. The traveling salesman problem is a famous example of a problem which can be solved by a branch and bound algorithm. To the right is a fragment from the optimal tour of all 24978 populated towns in Sweden, which is one of the largest traveling salesman problems solved to date. A parallel branch and bound algorithm was used to find this tour and then prove that no other tour could be shorter.

Uniprocessor Mapping

The uniprocessor mapping of branch and bound algorithms is straightforward: the processor explores the search space, using problem specific heuristics to guide the search into productive regions of the space, and then using problem specific bounding methods at each node of the search process.

Parallel Mapping

Branch and bound algorithms are often amenable to parallelization because of the searching nature of the optimization process. The search space can be divided such that each processor owns a different subregion, and then each processor can explore independently. In such an approach, dynamic load balancing issues are of crucial importance, since dividing up the search space amongst available processors effectively imposes a certain branching, and it is not possible in general to know a good branching strategy a priori which will keep all processors equally busy.

The tree structure at the top of this page, encountered during the solution of a trivial Boolean Satisfiability problem, illustrates this phenomenon. The unpredictable and irregular structure a branch and bound tree encounters during the solution process makes dynamic load balancing critical, especially if the bounding computation carried out at each node of the tree is relatively simple. Many branch and bound algorithms learn useful invariants about the search space during the solution process, such as cutting planes for Integer Linear Programming and learned clauses in Boolean Satisfiability. In a parallel branch and bound algorithm, these invariants cause inefficiency, since ideally they should be communicated between all solver processes in a fully connected fashion in order to avoid duplication and wasted effort. Also, many such invariants are potentially learned during the solution process, which can create large amounts of interprocess communication.

Elaboration

Credits

Traveling Salesman Problem at Georgia Tech

References

J. Eckstein, C. A. Phillips, and W. E. Hart, PICO: An Object-Oriented Framework for Parallel Branch and Bound, RUTCOR Research Report 40-2000, Rutgers University, Piscataway, NJ (2000).

V. Kumar and A. Gupta, Analyzing Scalability of Parallel Algorithms and Architectures, Journal of Parallel and Dsitributed Computing 22 (1994), 379.

B. Gendron and T. G. Crainic, Parallel Branch and Bound Algorithms: Survey and Synthesis, Operations Research 42 (1994), 1042.

Original text by Bryan Catanzaro.

Personal tools