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 https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_16714.tif"/> nodes is 22!/2 or around 8 × 10 14 https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_16715.tif"/> 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.
