用强化学习学分支策略，让求解整数规划更快。
Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization
- 用内部模型模拟分支过程，规划更优的变量选择
- 在4个标准测试集上超越现有最强强化学习方法
- 适合想提升整数规划求解效率的研究者
混合整数线性规划（MILP）是许多现实世界组合优化问题的核心，传统上通过分支定界法（B&B）求解。影响求解效率的关键因素是变量选择启发式策略。为突破静态人工设计启发式的局限，近期研究尝试将强化学习（RL）应用于B&B框架，以学习针对特定MILP分布的分支策略。与此同时，强化学习在棋类游戏中的成功得益于利用环境模拟器进行蒙特卡洛树搜索（MCTS）来规划。受此启发，我们提出计划-分支定界法（PlanB&B），一种基于模型的强化学习（MBRL）代理，通过学习B&B动态的内部模型，发现更优的分支策略。计算实验验证了该方法的有效性，其在四个标准MILP基准测试中均优于先前最先进的强化学习方法。
原文摘要 · Abstract (English)
Mixed-Integer Linear Programming (MILP) lies at the core of many real-world combinatorial optimization (CO) problems, traditionally solved by branch-and-bound (B&B). A key driver influencing B&B solvers efficiency is the variable selection heuristic that guides branching decisions. Looking to move beyond static, hand-crafted heuristics, recent work has explored adapting traditional reinforcement learning (RL) algorithms to the B&B setting, aiming to learn branching strategies tailored to specific MILP distributions. In parallel, RL agents have achieved remarkable success in board games, a very specific type of combinatorial problems, by leveraging environment simulators to plan via Monte Carlo Tree Search (MCTS). Building on these developments, we introduce Plan-and-Branch-and-Bound (PlanB&B), a model-based reinforcement learning (MBRL) agent that leverages a learned internal model of the B&B dynamics to discover improved branching strategies. Computational experiments empirically validate our approach, with our MBRL branching agent outperforming previous state-of-the-art RL methods across four standard MILP benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。