EUVIMEDEUVIMED entdecken
Crossref

Relaxations for Binary Polynomial Optimization via Signed Certificates

Liding Xu, Leo Liberti

Mathematics of Operations Research · 25.06.2026

DOI: 10.1287/moor.2024.0534 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, online erschienen am 25.06.2026. Verfasst von Liding Xu und 1 weiteren Autor:innen. Die Arbeit nennt 80 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the problem of minimizing a polynomial f over the (binary) hypercube. We show that, for a specific set of polynomials, their binary nonnegativity (i.e., on the hypercube) can be checked in polynomial time via minimum cut algorithms, from which we construct a linear programming representation for this set of polynomials. We categorize binary polynomials according to their signed support patterns and develop parameterized linear programming representations for binary nonnegative polynomials. This allows the construction of signed certificates of binary nonnegativity with adjustable signed support patterns and representation complexities; and we propose a method for minimizing f by decomposing it as a sum of signed certificates. This method yields new hierarchies of linear programming relaxations for binary polynomial optimization. Moreover, because our decomposition depends only on the support of f, the new hierarchies are sparsity-preserving. Funding: Most of the work done by the first author on this paper occurred while he was a PhD student at Laboratoire d’Informatique de l’École Polytechnique, Centre National de la Recherche Scientifique, École Polytechnique, Institut Polytechnique de Paris (IPP), sponsored by a grant of the IPP doctoral school, for which both authors are grateful.

Zitieren

APA

Xu, L., & Liberti, L. (2026). Relaxations for Binary Polynomial Optimization via Signed Certificates. Mathematics of Operations Research. https://doi.org/10.1287/moor.2024.0534

Vancouver

Xu L, Liberti L. Relaxations for Binary Polynomial Optimization via Signed Certificates. Mathematics of Operations Research. 2026. doi:10.1287/moor.2024.0534

BibTeX
@article{Xu2026,
  author = {Xu, Liding and Liberti, Leo},
  title = {Relaxations for Binary Polynomial Optimization via Signed Certificates},
  journal = {Mathematics of Operations Research},
  year = {2026},
  doi = {10.1287/moor.2024.0534}
}
Kostenlos starten →