Implementation and Testing of a Branch-and-Bound Based Method for Deterministic Global Optimization: Operations Research Applications

There are a variety of problems in production planning, transportation, finance, inventory, resource allocation and elsewhere where a guaranteed global optimum, rather than just a local optimum, is desired. Probabilistic approaches, based on various ideas such as using random multiple start points with the algorithms, have been useful. It would be satisfying, however, to have a guarantee of finding truly best solutions to nonlinear/nonconvex models. We describe a deterministic global solver that is based on several ideas: a) converting the original nonlinear/nonconvex into several linear/convex subproblems, b) using a Convex, Interval, and Algebraic(CIA) analysis, and c) a branch-and-bound technique to exhaustively search over these subproblems for the global solution. A distinctive feature of the implementation is the wide range of mathematical functions recognized. Computational results demonstrate the usefulness of the approach on a variety of types of problems: mixed-integer nonlinear, logic-based disjunctive, multi-user equilibria/complementarity, pooling/multi-level blending, nonlinear regression models, and models with standard probability functions such as the Normal distribution.