Branching and bounds tighteningtechniques for non-convex MINLP

Abstract

Many industrial problems can be naturally formulated using mixed integer non-linear programming (MINLP) models and can be solved by spatial Branch&Bound (sBB) techniques. We study the impact of two important parts of sBB methods: bounds tightening (BT) and branching strategies. We extend a branching technique originally developed for MILP, reliability branching, to the MINLP case. Motivated by the demand for open-source solvers for real-world MINLP problems, we have developed an sBB software package named couenne (Convex Over- and Under-ENvelopes for Non-linear Estimation) and used it for extensive tests on several combinations of BT and branching techniques on a set of publicly available and real-world MINLP instances. We also compare the performance of couenne with a state-of-the-art MINLP solver.

Keywords:

• mixed-integer non-linear programming
• Couenne
• branching rules
• bounds tightening

AMS Subject Classification :

• 90C11
• 90C26
• 90C57

Acknowledgements

This research was conducted while the first author was a postdoctoral fellow at the Tepper School of Business, Carnegie Mellon University. This research was conducted under an Open Collaboration Research Agreement between the IBM Corporation and Carnegie Mellon University, a grant from the IBM Corporation, and NSF Grant OCI07500826. One of the authors (L.L.) was partially supported by grants ANR-07-JCJC-0151 and Digiteo-RMNCCO.

Notes

A convex MINLP is an MINLP whose continuous relaxation is a convex NLP.

Available at svn at https://projects.coin-or.org/svn/Bonmin/branches/Couenne-0.9-candidate.

Running times and remaining gaps are taken as ‘equal’ if they do not differ by more than 10%.