The Running Intersection Relaxation of the Multilinear Polytope

• 成果类型: Article
• 署名作者: Del Pia, Alberto; Khajavirad, Aida
• 署名单位: University of Wisconsin System; University of Wisconsin Madison; Lehigh University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1121
• 发表日期: 2021
• 页码: 1008-1037
• 关键词: Optimization; nonconvex

摘要

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.