Branch and bound

From Glossary

Jump to: navigation, search

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)
                 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


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

Personal tools