用机器学习加速大规模优化问题求解,仅损失少量精度。
Fusing Backdoors, Machine Learning, and Optimization for Large-Scale Parametric Mixed-Integer Programs

- 识别影响计算复杂度的关键变量(后门变量),缩小求解范围。
- 预测后门变量值,将原问题简化为更小的子问题,提速显著。
- 适合频繁调整参数的场景,如电网、供应链等实时调度需求。
大规模优化问题常在结构相似但参数变化的情况下重复求解,带来巨大计算开销。本文提出BIPC框架,通过引入‘后门’概念——即决定计算复杂度的一组关键变量——来加速求解。该框架分三阶段:第一阶段识别分布内实例的后门变量;第二阶段使用监督学习模型,对有界域后门变量预测具体值,对宽域变量预测区间;由此构建约束后门变量的简化优化问题;第三阶段求解简化问题,必要时进行校正以恢复可行性或最优性保证。在真实世界大规模问题上的实验表明,该方法显著降低求解时间,仅带来有限的解质量损失。该框架适用于参数频繁扰动的场景,如突发事件、需求波动或运营变更,可高效集成至现有优化流程中。
原文摘要 · Abstract (English)
Large-scale optimization problems are often solved repeatedly under similar structural conditions, leading to substantial computational overhead. This occurs in applications such as power systems, transportation, and supply chain networks, where the underlying structure is fixed while parameters frequently vary under perturbations. This paper proposes a Learning to Optimize (LTO) framework that accelerates the solution of large-scale general mixed-integer problems by leveraging the concept of a backdoor, i.e., a subset of variables that drive most of the computational complexity. The proposed BIPC framework consists of three phases. Phase I is an identification procedure that discovers a backdoor for a set of instances in the distribution. Phase II uses supervised learning to develop machine learning models that, given an instance, predict values for bounded-domain backdoor variables and intervals for wide-domain backdoor variables. These predictions define a reduced optimization problem where the predictions constrain the backdoor variables, while the other variables remain free. Phase III optimizes this reduced problem and, if necessary, applies a correction step to restore feasibility or the optimality guarantees. Experiments on real-world, large-scale problems show substantial reductions in solution time with only a limited loss in solution quality. The framework enables organizations to solve large-scale optimization problems efficiently in the presence of frequent perturbations, such as unexpected events, demand fluctuations, or operational changes. Because these changes affect parameters rather than the problem structure, BIPC can quickly provide high-quality, feasible solutions, offering a practical approach to integrating machine learning into existing optimization pipelines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。