Branching and bounds tighteningtechniques for non-convex MINLP

Pietro Belotti*, Jon Lee, Leo Liberti, François Margot, Andreas Wächter

*Corresponding author for this work

Research output: Contribution to journalArticle

324 Scopus citations

Abstract

Many industrial problems can be naturally formulated using mixed integer non-linear programming (MINLP) models and can be solved by spatial BranchBound (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.

Original languageEnglish (US)
Pages (from-to)597-634
Number of pages38
JournalOptimization Methods and Software
Volume24
Issue number4-5
DOIs
StatePublished - Aug 2009

Keywords

  • Bounds tightening
  • Branching rules
  • Couenne
  • Mixed-integer non-linear programming

ASJC Scopus subject areas

  • Software
  • Control and Optimization
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Branching and bounds tighteningtechniques for non-convex MINLP'. Together they form a unique fingerprint.

  • Cite this