Optimization Online


On the impact of running intersection inequalities for globally solving polynomial optimization problems

Alberto Del Pia (delpia***at***wisc.edu)
Aida Khajavirad (aida***at***cmu.edu)
Nikolaos Sahinidis (sahinidis***at***cmu.edu)

Abstract: We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of a set of binary points satisfying a number of multilinear equations. Running intersection inequalities are a family of facet-defining inequalities for the multilinear polytope. In this paper we address the separation problem for this class of inequalities. We first prove that separating flower inequalities, a subclass of running intersection inequalities, is NP-hard. Subsequently, for multilinear polytopes of fixed degree, we devise an efficient polynomial-time algorithm for separating running intersection inequalities and embed the proposed cutting-plane generation scheme at every node of the branch-and-reduce global solver BARON. We carry out an extensive computational study on multilinear and polynomial optimization problems of degree three and four. Results show that running intersection cuts significantly improve the performance of BARON and lead to an average 50% CPU time reduction.

Keywords: branch-and-cut; polynomial optimization; running-intersection inequalities; multilinear polytope; separation algorithm; mixed-integer nonlinear optimization

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

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Global Optimization (Theory )

Citation: Submitted manuscript

Download: [PDF]

Entry Submitted: 06/29/2018
Entry Accepted: 06/29/2018
Entry Last Modified: 07/11/2019

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 Optimization Society