The Running Intersection Relaxation of the Multilinear Polytope
针对超图的多线性多面体，提出了一类新的运行交集不等式，定义了运行交集松弛，并证明在无风筝β-无环超图上该松弛与多线性多面体一致且有多项式大小扩展公式。
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.