The Proxy Benders Decomposition
Published in arXiv preprint arXiv:2606.07403, 2026
Changkun Guan, El Mehdi Er Raqabi, Mathieu Tanneau, Pascal Van Hentenryck. "The Proxy Benders Decomposition." arXiv preprint arXiv:2606.07403, 2026.
Classical Benders decomposition relies on repeatedly solving subproblems to optimality. The Proxy Benders Decomposition (Proxy-BD) replaces subproblem optimization with certified optimization proxies: a self-supervised predict-project-and-complete mechanism that produces dual-feasible solutions and therefore provably valid Benders cuts. A certification layer maintains theoretical validity regardless of prediction accuracy, and the approach extends to modern decomposition schemes.
On large uncapacitated facility location instances, Proxy-BD achieves median optimality gaps below 0.5%, yields up to 161× median speedups, and reduces the number of generated cuts by more than 240× on the largest instances.