Optimization Online


The running intersection relaxation of the multilinear polytope

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

Abstract: The multilinear polytope MP_G of a hypergraph G is the convex hull of a set of binary points satisfying a collection of multilinear equations. We introduce the running-intersection inequalities, a new class of facet-defining inequalities for the multilinear polytope. Accordingly, we define a new polyhedral relaxation of MP_G referred to as the running-intersection relaxation and identify conditions under which this relaxation is sharp. Namely, we show that for beta-acyclic hypergraphs with the simple intersection property, a class that lies between gamma-acyclic and beta-acyclic hypergraphs, the polytope MP_G admits a polynomial-size extended formulation whose projection onto the original space coincides with the running-intersection relaxation.

Keywords: multilinear polytope; running intersection property; hypergraph acyclicity; mixed- integer nonlinear optimization; polyhedral relaxations; extended formulations

Category 1: Integer Programming (0-1 Programming )

Category 2: Global Optimization (Theory )

Category 3: Combinatorial Optimization (Polyhedra )

Citation: submitted manuscript

Download: [PDF]

Entry Submitted: 05/09/2018
Entry Accepted: 05/10/2018
Entry Last Modified: 09/30/2020

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