A polyhedral branch-and-cut approach to global optimization

Mohit Tawarmalani, Nikolaos V. Sahinidis

Research output: Contribution to journalArticlepeer-review

Abstract

A variety of nonlinear, including semidefinite, relaxations have been developed in recent years for nonconvex optimization problems. Their potential can be realized only if they can be solved with sufficient speed and reliability. Unfortunately, state-of-the-art nonlinear programming codes are significantly slower and numerically unstable compared to linear programming software. In this paper, we facilitate the reliable use of nonlinear convex relaxations in global optimization via a polyhedral branch-and-cut approach. Our algorithm exploits convexity, either identified automatically or supplied through a suitable modeling language construct, in order to generate polyhedral cutting planes and relaxations for multivariate nonconvex problems. We prove that, if the convexity of a univariate or multivariate function is apparent by decomposing it into convex subexpressions, our relaxation constructor automatically exploits this convexity in a manner that is much superior to developing polyhedral outer approximators for the original function. The convexity of functional expressions that are composed to form nonconvex expressions is also automatically exploited. Root-node relaxations are computed for 87 problems from globallib and minlplib, and detailed computational results are presented for globally solving 26 of these problems with BARON 7.2, which implements the proposed techniques. The use of cutting planes for these problems reduces root-node relaxation gaps by up to 100% and expedites the solution process, often by several orders of magnitude.

Original languageEnglish (US)
Pages (from-to)225-249
Number of pages25
JournalMathematical Programming
Volume103
Issue number2
DOIs
StatePublished - Jun 2005

Keywords

  • Convexification
  • Convexity identification
  • Factorable programming
  • Mixed-integer nonlinear programming
  • Outer approximation

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'A polyhedral branch-and-cut approach to global optimization'. Together they form a unique fingerprint.

Cite this