(89c) Solving Large Nonconvex Models with a Deterministic Global Optimization Solver

There are a variety of problems in production planning, process design and synthesis, supply chain management, resource allocation, chemical equilibrium, and elsewhere where a guaranteed global optimum, rather than just a local optimum, is desired. There is a wide array of nonlinear solvers available to solve such complex problems. However, traditional solvers are not able to cope with the challenge of finding the truly best solutions with a certainty. 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 the implementation of a deterministic global solver that is based on several ideas: a) converting the original nonlinear/nonconvex into several linear/convex subproblems, b) using a combination of interval analysis, constraint propagation and algebraic reformulation, 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, including smooth, nonsmooth, and not quite continuous functions, logical and operational operators, and probability distributions.

In this paper, we describe our experience in solving practical nonlinear/nonconvex/nonsmooth/integer models to proven global optimum, based on new methods for reducing the convex relaxation gap and locating good solutions fast. Experience solving large spreadsheet nonconvex models demonstrates the ability to solve up to10,000 variable problems arising in: process synthesis, process operation, nonlinear regression, power plant scheduling, and multi-period planning.