用机器学习压缩大规模整数规划问题,速度比商用求解器快上百倍。
Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction
- 通过学习模型简化替代原问题,提升可解释性与求解效率。
- 相比顶尖方法,求解准确率提升近20%;比Gurobi快2至4个数量级。
- 结合偏好学习与注意力机制,适配复杂工业优化场景。
利用混合整数线性规划(MILP)结构与解之间的相关性,机器学习成为求解大规模MILP问题的有力工具。现有基于ML的求解器多采用端到端直接学习最优解,但受限于解空间高维性,难以扩展。本文不直接学习最优解,而是学习原MILP的简化等价模型作为中间步骤。该简化模型通常对应可解释操作且更简单,使我们能比现有商业求解器更快地解决大规模MILP问题。然而,当前方法仅依赖最优简化模型,忽视所有简化模型间的相对表现偏好信息。为此,本文提出一种基于偏好的模型简化学习方法,将每个MILP实例上所有简化模型的性能(目标代价与约束可行性)视为偏好。我们引入注意力机制以捕捉并表示偏好信息,从而提升模型简化学习效果。此外,提出基于SetCover的剪枝方法控制简化模型数量(即标签数),降低学习复杂度。在真实世界MILP问题上的评估表明:1)相比最先进模型简化方法,本方法在求解准确率上提升近20%;2)相比商业求解器Gurobi,实现2至4个数量级的速度提升。
原文摘要 · Abstract (English)
By exploiting the correlation between the structure and the solution of Mixed-Integer Linear Programming (MILP), Machine Learning (ML) has become a promising method for solving large-scale MILP problems. Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high dimensionality of the solution space. Instead of directly learning the optimal solution, this paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. However, current approaches rely only on the optimal reduced model, overlooking the significant preference information of all reduced models. To address this issue, this paper proposes a preference-based model reduction learning method, which considers the relative performance (i.e., objective cost and constraint feasibility) of all reduced models on each MILP instance as preferences. We also introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks. Moreover, we propose a SetCover based pruning method to control the number of reduced models (i.e., labels), thereby simplifying the learning process. Evaluation on real-world MILP problems shows that 1) compared to the state-of-the-art model reduction ML methods, our method obtains nearly 20% improvement on solution accuracy, and 2) compared to the commercial solver Gurobi, two to four orders of magnitude speedups are achieved.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。