The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909233447960576 |
|---|---|
| author | Del Pia, Alberto Khajavirad, Aida |
| author_facet | Del Pia, Alberto Khajavirad, Aida |
| contents | With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the convex hull of the set of binary points satisfying a collection of equations containing pseudo-Boolean functions. By representing the pseudo-Boolean polytope via a signed hypergraph, we obtain sufficient conditions under which this polytope has a polynomial-size extended formulation. Our new framework unifies and extends all prior results on the existence of polynomial-size extended formulations for the convex hull of the feasible region of binary polynomial optimization problems of degree at least three. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_08693 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization Del Pia, Alberto Khajavirad, Aida Optimization and Control Discrete Mathematics With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the convex hull of the set of binary points satisfying a collection of equations containing pseudo-Boolean functions. By representing the pseudo-Boolean polytope via a signed hypergraph, we obtain sufficient conditions under which this polytope has a polynomial-size extended formulation. Our new framework unifies and extends all prior results on the existence of polynomial-size extended formulations for the convex hull of the feasible region of binary polynomial optimization problems of degree at least three. |
| title | The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2309.08693 |