The Running Intersection Relaxation of the Multilinear Polytope

Alberto Del Pia () and Aida Khajavirad ()
Additional contact information
Alberto Del Pia: Department of Industrial and systems Engineering and Wisconsin Institute for Discovery, University of Wisconsin-Madison, Madison, Wisconsin 53706
Aida Khajavirad: Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, Pennsylvania 18015

Mathematics of Operations Research, 2021, vol. 46, issue 3, 1008-1037

Abstract: The multilinear polytope of a hypergraph 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 the multilinear polytope, referred to as the running intersection relaxation, and identify conditions under which this relaxation is tight. Namely, we show that for kite-free beta-acyclic hypergraphs, a class that lies between gamma-acyclic and beta-acyclic hypergraphs, the running intersection relaxation coincides with the multilinear polytope and it admits a polynomial size extended formulation.

Keywords: Primary: 90C10, 90C26, secondary: 90C11, 90C57, Primary: programming: integer: theory; programming: integer: nonlinear, secondary: programming: integer: cutting plane-facet generation, multilinear polytope, running intersection property, hypergraph acyclicity, polyhedral relaxations, extended formulations (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1121 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:3:p:1008-1037

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().