# Branch and bound

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.

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

B&B terminates when the list becomes empty, and the best feasible solution obtained is $LaTeX: x^*$ with value $LaTeX: f^*$, which is within $LaTeX: t$ of optimality. (If $LaTeX: f^* = -\infty$, then there is no feasible solution.) Notes:

1. 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.
2. 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 $LaTeX: x_j$, which could be $LaTeX: 0$ or $LaTeX: 1$. The breadth-first rule would solve the LPs for each of the two cases. The depth-first rule would solve for $LaTeX: x_j=0$ and postpone the complementary case, $LaTeX: x_j=1$ to consider another variable dichotomy, going deeper into the search tree. To illustrate, the following are search progressions in $LaTeX: \{0, 1\}^2$;.

         ____.                 ____.____          ____.____
|                     |         |        |         |
(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


3. 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.
4. 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.
5. 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.
6. The B&B methods we consider in OR are special cases of heuristic search in Artificial Intelligence (AI).