用代理模型替代重复求解子问题,显著加速大规模优化求解。
The Proxy Benders Decomposition

- 用自监督代理预测并生成可验证的割平面,避免反复精确求解子问题。
- 在2000×2000设施选址问题上,平均最优性差距低于0.5%,速度提升最高161倍。
- 适合处理复杂子问题的大规模分解优化,尤其在高复杂度场景下优势明显。
Benders分解是求解含复杂变量的大规模混合整数优化问题的基础框架,但经典方法常因重复求解高度相似的子问题且迭代中出现锯齿震荡,导致收敛缓慢。本文提出代理Benders分解(Proxy-BD),用经认证的优化代理替代子问题的重复精确求解。该代理采用自监督预测-投影-补全机制,生成可证明有效的对偶可行解以构造割平面。通过投影-补全认证层,保证分解理论有效性不受预测质量影响。建立了代理生成割平面的理论表征,框架可自然扩展至现代分解算法,如分支-割平面法。在大规模设施选址与网络设计问题上的实验表明,Proxy-BD显著降低子问题计算开销,同时保持接近最优解质量。在最大规模的无容量设施选址实例(2000×2000)上,中位最优性间隙低于0.5%,中位加速比达161倍,生成割平面数量减少超过240倍。计算增益随后置问题复杂度提升而持续增长,表明代理推理在大规模分解中相比重复精确求解具有更优可扩展性。
原文摘要 · Abstract (English)
Benders decomposition is a fundamental framework for solving large-scale mixed-integer optimization problems with complicating variables that, when fixed, yield significantly easier subproblems. However, classical Benders decomposition repeatedly solves highly similar subproblems and often exhibits zigzagging behavior across iterations, leading to slow convergence in large-scale settings. Motivated by the repetitive structure and parametric nature of Benders subproblems, this paper introduces the proxy Benders decomposition (Proxy-BD), a new decomposition framework in which subproblem optimization is replaced by certified optimization proxies rather than repeated exact solves. The proposed proxy follows a self-supervised predict-project-and-complete mechanism that produces dual-feasible solutions for generating provably valid Benders cuts. The framework preserves the theoretical validity of the decomposition independently of prediction quality through a projection-and-completion certification layer. A formal characterization of proxy-induced cuts is established, and the framework naturally extends to modern decomposition schemes, including branch-and-Benders-cut algorithms. Computational experiments on large-scale facility location and network design problems demonstrate that Proxy-BD substantially reduces the computational effort of subproblems while maintaining near-optimal solution quality. On large-scale uncapacitated facility location instances up to 2000x2000, Proxy-BD achieves median optimality gaps below 0.5%, yields up to 161x median speedups, and reduces the number of generated cuts by more than 240x on the largest instances. The computational gains consistently increase with recourse complexity, indicating that proxy-based inference scales substantially more favorably than repeated exact subproblem optimization in large-scale decomposition settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。