Branching and bounds tightening techniques for non-convex MINLP

Pietro Belotti (belotticmu.edu)
Jon Lee (jonleeus.ibm.com)
Leo Liberti (libertilix.polytechnique.fr)
Francois Margot (fmargotandrew.cmu.edu)
Andreas Waechter (andreaswus.ibm.com)

Abstract: 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.

Keywords: MINLP, spatial branch and bound, non-convex, global optimization

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Global Optimization

Citation: IBM Research Report RC24620

Download: [PDF]

Entry Submitted: 08/02/2008
Entry Accepted: 08/02/2008
Entry Last Modified: 08/25/2008

Modify/Update this entry