# Branch and bound

### From Glossary

Born in integer programming (IP), branch and bound (B&B) is more generally used in global optimization, including continuous functions. A prototype is as
follows.

*Initialize*set list with feasible region ( plus all constraints), say , with associated bounds , (finite bounds on the objective can be computed, if computationally preferable, and the initial set could be a superset of the feasible region). Initialize equal to the lower bound (, unless an initial feasible solution is known).*Branch*by selecting the -th set from list, say , and splitting into a partition, say such that the interior of does not intersect the interior of . (Could partition into more than 2 subsets.)*Bound*in and/or in , say for all , for and/or . Define if it is determined that is empty (in which case will be discarded in the next step).*Test*if , for and/or . If not, put on list. (If the test passes, is discarded by not being put on the list. Note: is best solution value to date, and is a tolerance that says we want to get a solution whose objective value is within of the optimal value.) Further, if and the associated point, , is feasible (where ), replace with and with . If the list is not empty, go to branch.

B&B terminates when the list becomes empty, and the best feasible solution obtained is with value , which is within of optimality. (If , then there is no feasible solution.) Notes:

- A particular bounding rule for IP is to solve an LP relaxation, whose value is an upper bound on the integer-valued maximum. The lower bounds do not change unless an integer solution is obtained from the LP, in which case the best solution to date can change.
- Branching rules can range from
*breadth-first*, i.e. expand all possible branches from a node in the search tree before going deeper into the tree, to*depth-first*, i.e. expand the deepest node first (and*backtrack*, as necessary). For example, suppose we branch on the value of , which could be or . The breadth-first rule would solve the LPs for each of the two cases. The depth-first rule would solve for and postpone the complementary case, to consider another variable dichotomy, going deeper into the search tree. To illustrate, the following are search progressions in ;.Breadth-first:

____. ____.____ ____.____ | | | | | (x=0) (x=0) (x=1) (x=0) (x=1) / (y=0) 1 2 3 ____.____ ____.____ ____.____ | | | | | | (x=0) (x=1) (x=0) (x=1) (x=0) (x=1) /\ /\ / /\ /\ (y=0)(y=1) (y=0)(y=1) (y=0) (y=0)(y=1) (y=0)(y=1) 4 5 6

Depth-first:

____. ____. ____. | | | (x=0) (x=0) (x=0) / /\ (y=0) (y=0)(y=1) 1 2 3 ____.____ ____.____ ____.____ | | | | | | (x=0) (x=1) (x=0) (x=1) (x=0) (x=1) /\ /\ / /\ /\ (y=0)(y=1) (y=0)(y=1) (y=0) (y=0)(y=1) (y=0)(y=1) 4 5 6

- A
*best-first*search is to select the node (i.e., set on list) that seems most promising, such as one with the greatest upper bound. Typically, there are multiple criteria for branching, and these change depending on whether a feasible solution has been obtained. - Backtracking need not go in exactly the reverse order (i.e.,
need not have a LIFO rule), but care must be taken when
*reordering*the path. - When the problem is not finite (not IP), branching rules need to consider the hyper-volume of each set in a partition to ensure convergence.
- The B&B methods we consider in OR are special cases of heuristic search in Artificial Intelligence (AI).