Back to SYMPHONY Home Page

Branch and Bound

Branch and bound is the broad class of algorithms from which branch, cut, and price is descended. Branch and bound algorithms use a divide and conquer strategy to partition the solution space into subproblems and then optimizes individually over each of them. For instance, let S be the set of solutions to a given problem, and let $c \in {\bf R}^S$ be a vector of costs associated with members of S. Suppose we wish to determine a least cost member of S and we are given $\hat{s} \in S$, a ``good'' solution determined heuristically. Using branch and bound, we initially examine the entire solution space S. In the processing or bounding phase, we relax the problem in some fashion. In so doing, we admit solutions that are not in the feasible set S. Solving this relaxation yields a lower bound on the value of an optimal solution. If the solution to this relaxation is a member of S or has cost equal to $\hat{s}$, then we are done--either the new solution or $\hat{s}$, respectively, is optimal. Otherwise, we identify n subsets of S, $S_1, \ldots, S_n$, such that $\cup_{i = 1}^n S_i = S$. Each of these subsets is called a subproblem; $S_1, \ldots, S_n$ are also sometimes called the children of S. We add the children of S to the list of candidate subproblems (those which need processing). This is called the branching phase.

To continue the algorithm, we select one of the candidate subproblems and process it. There are four possible results. If we find a feasible solution better than $\hat{s}$, then we replace $\hat{s}$ with the new solution and continue. We may also find that the subproblem has no solutions, in which case we discard, or prune it. Otherwise, we compare the lower bound to our global upper bound. If it is greater than or equal to our current upper bound, then we may again prune the subproblem. Finally, if all else fails, we are forced to branch and add the children of this subproblem to the list of active candidates. We continue in this way until the list of active subproblems is empty, at which point our current best solution is the optimal one.