Branch and Bound

algorithms

Definition

Branch and Bound

Branch and bound restricts the search over all solutions systematically based on divide and conquer, using methods that provide lower and upper bounds, and determines and optimal solution.

Branching: Partition the problem in smaller sub-problems ⇒ Divide and Conquer

Bounding: For every sub-problems, compute:

• local upper bound $U^{\prime }$
• local lower bound $L^{\prime }$

Let $L$ be the global lower bound of the current best solution. Sub-problems with $U^{\prime }\le L$ can be omitted in the search space.

The goal is to find the highest lower-bound $L$ possible for the given search space.

Selection Methods

Best-first Selection

The subproblem with the best dual boundaries (with the best upper boundary) is chosen. This always processes the smallest possible number of subproblems.

Depth-first Selection

The most recently created subproblem is processed next (compared with depth-first search). One usually obtains a complete and valid approximate solution most quickly.

Frequently, one starts with a depth-first strategy and, after obtaining a valid solution, continues with best-first to combine the advantages.