Optimization Online


Branching and bounds tightening techniques for non-convex MINLP

Pietro Belotti (belotti***at***cmu.edu)
Jon Lee (jonlee***at***us.ibm.com)
Leo Liberti (liberti***at***lix.polytechnique.fr)
Francois Margot (fmargot***at***andrew.cmu.edu)
Andreas Waechter (andreasw***at***us.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society