On Partial Optimality in QUBO via Quadratic Posiform Autarkies
Abstract
Partially optimal assignments (also called persistencies) allow combinatorial optimization problems to be reduced by fixing a subset of variables to values consistent with at least one optimal solution. For the quadratic unconstrained binary optimization (QUBO) problem, such assignments can be computed efficiently via autarkies of quadratic posiforms. However, the largest autarky domain and thus the number of fixed variables can depend on the specific posiform representation. We show that every quadratic posiform with the greatest possible constant term (the roof-dual bound) yields the largest autarky domain obtainable from any quadratic posiform. By computing such a roof-dual-optimal quadratic posiform and a corresponding autarky with largest domain in polynomial time, one can therefore attain the maximum partial optimality obtainable by quadratic posiform autarkies in polynomial time. This justifies the computation of roof-dual-optimal quadratic posiforms and corresponding autarkies in popular polynomial-time algorithms and establishes that finding additional partial optimality in QUBO requires going beyond autarkies of quadratic posiforms.
Related
- Optimality of Affine Policies in Distributionally Robust Linear-Quadratic Control with Temporally Correlated Noise
- A Behavioral approach to Constrained Linear Quadratic Control: Feasibility and Optimality
- Online Individualized Treatment Selection under Partial Feedback: False Discovery Control and Minimax Optimality
- Reusable QUBO-Derived Block-Schur Inverse Factors for Fixed-Operator Finite-Difference PDE Solvers
- GPU Parallel Pareto Local Search for Multi-objective QUBO
BibTeX
@misc{naumann2026partial,
title = {{On Partial Optimality in QUBO via Quadratic Posiform Autarkies}},
author = {Lucas Fabian Naumann and Bjoern Andres},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20346},
eprint = {2610.20346},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20346},
}
RIS
TY - UNPB
TI - On Partial Optimality in QUBO via Quadratic Posiform Autarkies
AU - Lucas Fabian Naumann
AU - Bjoern Andres
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20346
UR - https://arxiv.org/abs/2610.20346
AB - Partially optimal assignments (also called persistencies) allow combinatorial optimization problems to be reduced by fixing a subset of variables to values consistent with at least one optimal solution. For the quadratic unconstrained binary optimization (QUBO) problem, such assignments can be computed efficiently via autarkies of quadratic posiforms. However, the largest autarky domain and thus the number of fixed variables can depend on the specific posiform representation. We show that every quadratic posiform with the greatest possible constant term (the roof-dual bound) yields the largest autarky domain obtainable from any quadratic posiform. By computing such a roof-dual-optimal quadratic posiform and a corresponding autarky with largest domain in polynomial time, one can therefore attain the maximum partial optimality obtainable by quadratic posiform autarkies in polynomial time. This justifies the computation of roof-dual-optimal quadratic posiforms and corresponding autarkies in popular polynomial-time algorithms and establishes that finding additional partial optimality in QUBO requires going beyond autarkies of quadratic posiforms.
ER -