Polynomial Binary Optimization
Abstract
In a binary polynomial optimization problem (BPO, in short) we are maximizing a multilinear polynomial expression depending on n binary variables. This is a hard optimization class, containing many NP-hard problems, including unconstrained quadratic binary optimization. Several tractable special classes were considered in the literature, including problems with bounded tree-width (Crama, Hansen, Jaumard, 1990), Berge-acyclic problems (Buchheim, Crama, and Heck, 2019), β-acyclic problems (Del Pia and Di Gregorio, 2022, 2023), limited reach problems (Clausen, Crama, Lusby, Rodríguez, and Ropke, 2024), and α-acyclic problems with bounded rank (Del Pia and Khajavirad, 2025). We focus on a general variable elimination scheme for BPO, and develop the unique explicit multi-linear polynomial form for the equivalent BPO problem obtained after the elimination of a given subset of the variables. The obtained closed form representation of such an equivalent BPO problem allows us to characterize new special classes for which this elimination method, when applied recursively, provides a computationally efficient solution. Our approach is elementary1, algebraic, and provides efficient solution to a wide problem class that properly generalizes all of the above mentioned tractable special cases.
Related
- Circuit Design Problems in Binary Polynomial Quantum Optimization
- Binary dimension-free discretization and polynomial complexification on real cubes
- A Four-by-Four Obstruction to Polynomial Removal for Ordered Binary Matrices
- On the polynomial values represented by binary quadratic forms
- Optimal Control of State Constrained Systems via Measure Relaxations and Polynomial Optimization
BibTeX
@misc{boros2026polynomial,
title = {{Polynomial Binary Optimization}},
author = {Endre Boros},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.08908},
eprint = {2607.08908},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.08908},
}
RIS
TY - UNPB
TI - Polynomial Binary Optimization
AU - Endre Boros
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2607.08908
UR - https://arxiv.org/abs/2607.08908
AB - In a binary polynomial optimization problem (BPO, in short) we are maximizing a multilinear polynomial expression depending on n binary variables. This is a hard optimization class, containing many NP-hard problems, including unconstrained quadratic binary optimization. Several tractable special classes were considered in the literature, including problems with bounded tree-width (Crama, Hansen, Jaumard, 1990), Berge-acyclic problems (Buchheim, Crama, and Heck, 2019), β-acyclic problems (Del Pia and Di Gregorio, 2022, 2023), limited reach problems (Clausen, Crama, Lusby, Rodríguez, and Ropke, 2024), and α-acyclic problems with bounded rank (Del Pia and Khajavirad, 2025). We focus on a general variable elimination scheme for BPO, and develop the unique explicit multi-linear polynomial form for the equivalent BPO problem obtained after the elimination of a given subset of the variables. The obtained closed form representation of such an equivalent BPO problem allows us to characterize new special classes for which this elimination method, when applied recursively, provides a computationally efficient solution. Our approach is elementary1, algebraic, and provides efficient solution to a wide problem class that properly generalizes all of the above mentioned tractable special cases.
ER -