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.
Citation
submitted manuscript
Article