让早期求解结果指导最终解,加速整数规划求解
Learning Early-to-Final Solution Consistency for MILP Acceleration
- 用早期求解结果预测变量是否应保持不变
- 使目标函数差距平均降低56.9%,组合拍卖实例完全收敛
- 无需微调即可迁移到其他求解器,适合工业优化场景
混合整数线性规划(MILP)是运筹学与组合优化中的基础问题,广泛应用于工业决策。由于其NP难性,现代求解器在合理时间内难以获得高质量解。现有基于学习的方法通过静态实例特征(如变量-约束二分图)直接预测高质量解,但难以仅凭特征准确预测,且忽视求解过程中的动态信息。本文发现:求解器早期阶段的解往往在结构上接近全预算搜索后的解。受此启发,我们提出一种新范式,将学习目标从变量赋值转为早期到最终解的一致性预测:对每个变量,预测其早期赋值是否应在完整搜索中保留。该一致性预测可自然引导后续搜索(如固定一致变量)。推理时,通过集成多个早期解的一致性预测提升鲁棒性。在四个MILP基准上的实验表明,该方法显著提升多种下游搜索流程性能。使用Gurobi时,平均原始差距降低56.9%,组合拍卖实例实现完全闭合;此外,将Gurobi训练模型零样本迁移至SCIP,平均差距减少36.4%。
原文摘要 · Abstract (English)
Mixed-Integer Linear Programming (MILP) is a fundamental problem class in operations research and combinatorial optimization, with broad applications to industrial decision-making. Owing to their NP-hardness, however, modern solvers may struggle to find high-quality solutions for challenging MILP instances within practical time limits. Recent learning-based approaches seek to accelerate MILP solving by directly predicting high-quality solutions from static instance-level features, such as variable-constraint bipartite graphs. Yet accurate solution prediction from instance features alone is difficult, and these methods largely overlook the information revealed during the solver's search process. In this paper, we find that solutions produced at the early search stage of MILP solvers, which are computationally cheap to obtain, are often structurally close to the solutions found after full-budget search. Motivated by this observation, we propose a new solver-informed paradigm that shifts the learning target from variable assignment to early-to-final consistency: for each variable, we predict whether its early-stage assignment should persist in full-budget solutions. The predicted consistency naturally guides downstream search, for instance by fixing the assignments deemed consistent. At inference time, we further ensemble consistency predictions across multiple early-stage solutions to improve robustness. Experiments across four MILP benchmarks show our method improves prediction-guided search across diverse downstream pipelines. With Gurobi, our proposed method reduces the primal gap by 56.9% on average and closes it completely on combinatorial auction instances. Besides, we transferred the Gurobi-trained model zero-shot to SCIP without adaptation, achieving a 36.4% average gap reduction across benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。