- | ||||
|
![]()
|
The running intersection relaxation of the multilinear polytope
Alberto Del Pia (delpia Abstract: 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. Keywords: multilinear polytope; running intersection property; hypergraph acyclicity; mixed- integer nonlinear optimization; polyhedral relaxations; extended formulations Category 1: Integer Programming (0-1 Programming ) Category 2: Global Optimization (Theory ) Category 3: Combinatorial Optimization (Polyhedra ) Citation: submitted manuscript Download: [PDF] Entry Submitted: 05/09/2018 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |