Extended formulations for the multilinear polytope of acyclic hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916558309163008 |
|---|---|
| author | Del Pia, Alberto Khajavirad, Aida |
| author_facet | Del Pia, Alberto Khajavirad, Aida |
| contents | This article provides an overview of our joint work on binary polynomial optimization over the past decade. We define the multilinear polytope as the convex hull of the feasible region of a linearized binary polynomial optimization problem. By representing the multilinear polytope with hypergraphs, we investigate the connections between hypergraph acyclicity and the complexity of the facial structure of the multilinear polytope. We characterize the acyclic hypergraphs for which a polynomial-size extended formulation for the multilinear polytope can be constructed in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_04805 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Extended formulations for the multilinear polytope of acyclic hypergraphs Del Pia, Alberto Khajavirad, Aida Optimization and Control Discrete Mathematics This article provides an overview of our joint work on binary polynomial optimization over the past decade. We define the multilinear polytope as the convex hull of the feasible region of a linearized binary polynomial optimization problem. By representing the multilinear polytope with hypergraphs, we investigate the connections between hypergraph acyclicity and the complexity of the facial structure of the multilinear polytope. We characterize the acyclic hypergraphs for which a polynomial-size extended formulation for the multilinear polytope can be constructed in polynomial time. |
| title | Extended formulations for the multilinear polytope of acyclic hypergraphs |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2501.04805 |