Scaling Local Solvers with the Many-Body Expansion
Abstract
We introduce a Many-Body Expansion framework for scaling black-box solvers for discrete optimization. The method decomposes a large problem into fragments, repeatedly improves each fragment with the rest of the assignment held fixed, and then applies targeted corrections on unions of fragments. The solver itself is unchanged: it only receives a restricted subproblem and returns a candidate assignment. The framework separates decomposition from solver design. Moebius inversion gives an exact fragment expansion of the objective, and for pairwise objectives such as graph coloring, MAX-CUT, and QUBO the expansion closes at second order. The promoted solver is monotone by construction, terminates in finitely many productive sweeps for non-negative integer-valued objectives, and connects to junction-tree dynamic programming when the fragment interaction structure is acyclic and full response functions are propagated. On graph coloring benchmarks, the promoted versions of TabuSearch and simulated annealing (SA) generally outperform flat applications of the same solvers, often finding better solutions in less CPU time, and the gain proves insensitive to the choice of graph partition. A facility-location study delimits the claim: there the partition must respect the objective's interaction locality, and the promoted solver reaches within 0.3-1.4% of GLPK-certified optima at every tested size. The same wrapper interface is used in each solver-swap case, and the facility-location check reuses the same monotone guard with a sign-adjusted interaction diagnostic; the improvements therefore come from the MBE promotion mechanism rather than solver-specific tuning.
Related
- Impact of Feature Scaling on the Convergence Speed of Linear SVM Solvers : An Empirical Benchmark
- BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning
- Where, When, and How Many Bits? Scaling Laws for SGD with Stochastic Rounding
- Many-body localization: an introduction for mathematicians
- Fibonacci number systems and the localization criterion in the many-body Aubry-André model
BibTeX
@misc{zahariev2026scaling,
title = {{Scaling Local Solvers with the Many-Body Expansion}},
author = {Federico Zahariev and Amr Sabry},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30137},
eprint = {2610.30137},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30137},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Scaling Local Solvers with the Many-Body Expansion
AU - Federico Zahariev
AU - Amr Sabry
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.30137
UR - https://arxiv.org/abs/2610.30137
AB - We introduce a Many-Body Expansion framework for scaling black-box solvers for discrete optimization. The method decomposes a large problem into fragments, repeatedly improves each fragment with the rest of the assignment held fixed, and then applies targeted corrections on unions of fragments. The solver itself is unchanged: it only receives a restricted subproblem and returns a candidate assignment. The framework separates decomposition from solver design. Moebius inversion gives an exact fragment expansion of the objective, and for pairwise objectives such as graph coloring, MAX-CUT, and QUBO the expansion closes at second order. The promoted solver is monotone by construction, terminates in finitely many productive sweeps for non-negative integer-valued objectives, and connects to junction-tree dynamic programming when the fragment interaction structure is acyclic and full response functions are propagated. On graph coloring benchmarks, the promoted versions of TabuSearch and simulated annealing (SA) generally outperform flat applications of the same solvers, often finding better solutions in less CPU time, and the gain proves insensitive to the choice of graph partition. A facility-location study delimits the claim: there the partition must respect the objective's interaction locality, and the promoted solver reaches within 0.3-1.4% of GLPK-certified optima at every tested size. The same wrapper interface is used in each solver-swap case, and the facility-location check reuses the same monotone guard with a sign-adjusted interaction diagnostic; the improvements therefore come from the MBE promotion mechanism rather than solver-specific tuning.
ER -