The running intersection relaxation of the multilinear polytope

Alberto Del Pia (delpiawisc.edu)
Aida Khajavirad (aidacmu.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