Polynomial Binary Optimization
2026-07-09 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study a hard math problem where you try to maximize a polynomial with variables that can only be 0 or 1. They explore a way to simplify the problem by removing some variables and rewriting it as an equivalent polynomial, which helps solve certain special cases faster. Their new method extends previous known efficient cases and can be repeated to solve larger problems more easily. This approach is based on algebra and provides a clearer way to understand and tackle these optimization problems.
binary polynomial optimizationmultilinear polynomialvariable eliminationNP-hardtree-widthBerge-acyclicβ-acyclicα-acyclicalgebraic optimizationproblem tractability
Authors
Endre Boros
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.