Branch and Bound Methods

TLDR

Branch and bound algorithms are nonheuristic global optimization methods for nonconvex problems that maintain provable bounds and terminate with an ε‑suboptimal certificate, yet they can be slow, requiring exponential effort in the worst case but often converging with less effort. The notes aim to illustrate two simple branch and bound examples and present typical results for a minimum cardinality problem. The authors present two straightforward branch and bound formulations for the minimum cardinality problem and demonstrate their application. The results show that the simple branch and bound approaches successfully solve the minimum cardinality problem, illustrating their practical performance.

Abstract

Branch and bound algorithms are methods for global optimization in nonconvex problems [LW66, Moo91]. They are nonheuristic, in the sense that they maintain a provable upper and lower bound on the (globally) optimal objective value; they terminate with a certificate proving that the suboptimal point found is ǫ-suboptimal. Branch and bound algorithms can be (and often are) slow, however. In the worst case they require effort that grows exponentially with problem size, but in some cases we are lucky, and the methods converge with much less effort. In these notes we describe two typical and simple examples of branch and bound methods, and show some typical results, for a minimum cardinality problem.