Branching and Bounds Tightening Techniques for Non-Convex MINLP

Many industrial problems can be naturally formulated using Mixed Integer Nonlinear Programming (MINLP). Motivated by the demand for Open-Source solvers for real-world MINLP problems, we have developed a spatial Branch-and-Bound software package named couenne (Convex Over- and Under-ENvelopes for Nonlinear Estimation). In this paper, we present the structure of couenne and discuss in detail our work on two of its components: bounds tightening and branching strategies. We then present experimental results on a set of MINLP instances including some industrial applications. We also compare the performance of couenne with a state-of-the-art solver for nonconvex MINLPs.

By: Pietro Belotti; Jon Lee; Leo Liberti; Francois Margot; Andreas Waechter

Published in: Optimization Methods and Software, volume 24, (no 4-5), pages 597-634 in 2009

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .