A Development and Deployment Framework for Distributed Branch-and-Bound

Authored by: Peter Cappello , Christopher James Coakley

Handbook of Approximation Algorithms and Metaheuristics, Second Edition

Print publication date:  May  2018
Online publication date:  May  2018

Print ISBN: 9781498770118
eBook ISBN: 9781351236423
Adobe ISBN:

10.1201/9781351236423-35

 Download Chapter

 

Abstract

Branch-and-bound intelligently searches the set of feasible solutions to a combinatorial optimization problem. It, in effect, proves that the optimal solution is found without necessarily examining all feasible solutions. The feasible solutions are not given. They can be generated from the problem description. However, doing so usually is computationally infeasible. The number of feasible solutions typically grows exponentially as a function of the size of the problem input. For example, the set of feasible tours in a symmetric traveling salesman problem (TSP)of a complete graph with 23 nodes is 22!/2 or around 8 × 10 14 tours. The space of feasible solutions is progressively partitioned (branching), forming a search tree. Each tree node has a partial feasible solution. The node represents the set of feasible solutions that are extensions of its partial solution. For example, in a TSP branch-and-bound, a search tree node has a partial tour, representing the set of all tours that contain that partial tour. As branching continues (progresses down the problem tree), each search node has a more complete partial solution, and thus represents a smaller set of feasible solutions. For example, in a TSP branch-and-bound, a tree node’s children each represent an extension of the partial tour to a more complete tour (e.g., one additional city or one additional edge). As one progresses down the search tree, each node represents a larger partial tour. As the size of a partial tour increases, the number of full tours containing the partial tour clearly decreases.

 Cite
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.