让分支与割平面协同学习,提升整数规划求解效率
Collab-Solver: Collaborative Solving Policy Learning for Mixed-Integer Linear Programming
- 将割平面与分支策略建模为斯塔克尔伯格博弈,实现协同优化
- 在真实和合成数据集上,求解速度提升30%以上,解质量显著改善
- 适用于需要高效求解整数规划的工业场景,如物流调度、资源分配
整数线性规划(MILP)是组合优化中的基础问题。传统求解依赖分支定界框架中精心设计的启发式算法。近年来,机器学习展现出潜力,但现有方法通常孤立地学习各模块策略,忽视其相互依赖,限制了解决效率与质量。为此,我们提出Collab-Solver,一种基于多智能体的协作策略学习框架,实现多个模块的联合优化。具体地,将割平面选择与分支决策建模为斯塔克尔伯格博弈,并设计两阶段学习范式:第一阶段进行数据共享的预训练,第二阶段进一步协调各模块策略学习。在合成及大规模真实世界MILP数据集上的实验表明,联合学习的策略显著提升求解性能。此外,所学策略在不同实例集间展现出优异泛化能力。
原文摘要 · Abstract (English)
Mixed-integer linear programming (MILP) has been a fundamental problem in combinatorial optimization. Conventional MILP solving mainly relies on carefully designed heuristics embedded in the branch-and-bound framework. Driven by the strong capabilities of neural networks, recent research is exploring the value of machine learning alongside conventional MILP solving. Although learning-based MILP methods have shown great promise, existing works typically learn policies for individual modules in MILP solvers in isolation, without considering their interdependence, which limits both solving efficiency and solution quality. To address this limitation, we propose Collab-Solver, a novel multi-agent-based policy learning framework for MILP that enables collaborative policy optimization for multiple modules. Specifically, we formulate the collaboration between cut selection and branching in MILP solving as a Stackelberg game. Under this formulation, we develop a two-phase learning paradigm to stabilize collaborative policy learning: the first phase performs data-communicated policy pretraining, and the second phase further orchestrates the policy learning for various modules. Extensive experiments on both synthetic and large-scale real-world MILP datasets demonstrate that the jointly learned policies significantly improve solving performance. Moreover, the policies learned by Collab-Solver have also demonstrated excellent generalization abilities across different instance sets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。