Options
Scalable determination of penalization weights for constrained optimizations on approximate solvers
Citation Link: https://doi.org/10.15480/882.16944
Publikationstyp
Preprint
Date Issued
2026-04-02
Sprache
English
TORE-DOI
Citation
arXiv: 2604.02416 (2026)
Publisher DOI
ArXiv ID
Peer Reviewed
false
Quadratic unconstrained binary optimization (QUBO) provides problem formulations for various computational problems that can be solved with dedicated QUBO solvers, which can be based on classical or quantum computation. A common approach to constrained combinatorial optimization problems is to enforce the constraints in the QUBO formulation by adding penalization terms. Penalization introduces an additional hyperparameter that significantly affects the solver's efficacy: the relative weight between the objective terms and the penalization terms. We develop a pre-computation strategy for determining penalization weights with provable guarantees for Gibbs solvers and polynomial complexity for broad problem classes. Experiments across diverse problems and solver architectures, including large-scale instances on Fujitsu's Digital Annealer, show robust performance and order-of-magnitude speedups over existing heuristics.
Subjects
Constrained Optimizations Digital Annealer
DDC Class
004: Computer Sciences
510: Mathematics
519: Applied Mathematics, Probabilities
Publication version
submittedVersion
Loading...
Name
2604.02416v1.pdf
Type
Main Article
Size
5.48 MB
Format
Adobe PDF