Branch and Bound Algorithm

Branch and bound algorithms are a variety of adaptive partition strategies have been proposed to solve global optimization models. These are based upon partition, sampling, and subsequent lower and upper bounding procedures: these operations are applied iteratively to the collection of active ("candidate") subsets within the feasible set . Their exhaustive search feature is guaranteed in similar spirit to the analogous integer linear programming methodology. Branch and bound subsumes many specific approaches, and allows for a variety of implementations. Branch and bound methods typically rely on some a priori structural knowledge about the problem. This information may relate, for instance to how rapidly each function can vary (e.g., the knowledge of a suitable "overall" Lipschitz constant, for each function  and ); or to the availability of an analytic formulation and guaranteed smoothness of all functions (for instance, in interval arithmetic-based methods). The general branch and bound methodology is applicable to broad classes of global optimization problems, e.g., in combinatorial optimization, concave minimization, reverse convex programs, DC programming, and Lipschitz optimization (Neumaier 1990, Hansen 1992, Ratschek and Rokne 1995, Kearfott 1996, Horst and Tuy 1996, Pintér 1996).

REFERENCES:

Hansen, E. R. Global Optimization Using Interval Analysis. New York: Dekker, 1992.

Horst, R. and Tuy, H. Global Optimization: Deterministic Approaches, 3rd ed. Berlin: Springer-Verlag, 1996.

Kearfott, R. B. Rigorous Global Search: Continuous Problems. Dordrecht, Netherlands: Kluwer, 1996.

Neumaier, A. Interval Methods for Systems of Equations. Cambridge, England: Cambridge University Press, 1990.

Pintér, J. D. Global Optimization in Action. Dordrecht, Netherlands: Kluwer, 1996.

Ratschek, H. and Rokne, J. G. "Interval Methods." In Handbook of Global Optimization: Nonconvex Optimization and Its Applications (Ed. R. Horst and P. M. Pardalos). Dordrecht, Netherlands: Kluwer, pp. 751-828, 1995.