The Running Intersection Relaxation of the Multilinear Polytope

• DOI: 10.1287/moor.2021.1121
• Publication Date: 2021-04-20T12:40:20Z
• Authors: Alberto Del Pia; Aida Khajavirad
• Keywords: Convex polytope; Birkhoff polytope

The multilinear polytope of a hypergraph is the convex hull set binary points satisfying collection equations. We introduce running intersection inequalities, new class facet-defining inequalities for polytope. Accordingly, we define polyhedral relaxation polytope, referred to as relaxation, and identify conditions under which this tight. Namely, show that kite-free beta-acyclic hypergraphs, lies between gamma-acyclic coincides with it admits polynomial size extended formulation.