next up previous contents
Next: Branching and Bounding Up: The Optimization Previous: The choice of a   Contents

Branch and Bound

In the field of Discrete Optimization, Branch and Bound is a popular way of limiting the solution space to include only potentially relevant subspaces.

In short, the B&B algorithm begins in the root of the search tree. A number of branches is generated, and depending on the variant of the search (depth first, breadth first, best first, or hybrids), some branch is elected for exploration.

If we're able to predict what the smallest possible value we can ever get from our target function will be (the cost of factorizing the system given some row/column ordering), from descending some given branch, we are able to discard all branches we encounter which does not yield any possibility for an improvement (eg. a lower value of the target function). This is why the algorithm - quite intuitively - is called branch and bound.






1999-02-23