(398a) Third Generation Branch-and-Reduce Algorithms and Software

The development of the BARON algorithms and software for global optimization began in the early 1990s.  Initially, the software integrated factorable nonlinear relaxations within a domain-reduction-based branch-and-bound algorithm.  At that time, various feasibility- and optimality-based techniques were introduced for range reduction [1].  BARON became more widely used and recognized only when it entered its second phase of development, when nonlinear relaxations were replaced by polyhedral ones [2, 3] that increased its robustness and performance.  The third generation of branch-and-reduce algorithms began to appear with the introduction of relaxation techniques for simultaneous convexification of several quadratic terms [4]. 

In this talk, we propose techniques that are crucial in extending BARON’s simultaneous convexification techniques via polyhedral cutting planes to a variety of problems.  Key in our development is the observation that facets of polyhedral envelopes for a variety of nonlinear functions and constraint sets can be obtained by solving a specific linear optimization problem (LP).  When used as cutting planes, these facets can significantly enhance the quality of conventional relaxations in global solvers.  However, in general, the size of this LP grows exponentially with the number of variables in these nonlinear functions.  To cope with this growth, we propose a graph decomposition scheme that exploits the structure of the nonlinear function to decompose it to lower-dimensional components, for which the aforementioned LP can be solved very efficiently by employing a customized simplex algorithm.

We embed this cutting plane generation strategy at every node of the branch-and-reduce global solver BARON, and carry out an extensive computational study on quadratically constrained quadratic problems, multilinear problems, and polynomial optimization problems.  Results show that the proposed cuts enable BARON to solve many more problems to global optimality and result in considerable speed-ups of the algorithm.

Finally, other recent advances in the branch-and-reduce algorithm are summarized and extensive computational results are presented for large classes of standard problem sets.

 References cited:

1. Ryoo, H. S. and N. V. Sahinidis, Global optimization of nonconvex NLPs and MINLPs with applications in process design, Computers & Chemical Engineering, 19(5), 551-566, 1995.
2. Tawarmalani, M. and N. V. Sahinidis, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Mathematical Programming, 99(3), 563-591, 2004.
3. Tawarmalani, M. and N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization, Mathematical Programming, 103, 225-249, 2005.
4. Bao, X., N. V. Sahinidis, and M. Tawarmalani, Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs, Optimization Methods and Software, 24, 485-504, 2009.