用马尔可夫决策过程优化分支定界变量选择，提升求解效率
A Markov Decision Process for Variable Selection in Branch & Bound
- 构建标准马尔可夫决策过程模型，统一建模变量选择问题
- 在4个标准测试集上超越现有最先进强化学习方法
- 适用于希望改进整数规划求解器的算法研究者
混合整数线性规划（MILP）是解决大量NP难组合优化问题的强大框架，通常通过分支定界（B&B）求解。影响B&B求解器性能的关键因素是控制分支决策的变量选择启发式策略。近期工作尝试将强化学习（RL）算法应用于B&B场景，通过受马尔可夫决策过程（MDP）启发的建模方式与特定收敛定理来学习最优分支策略。本文提出BBMDP，一个用于变量选择的严谨且基础的MDP形式化模型，使多种强化学习算法可用于学习最优的B&B启发式策略。计算实验验证了该模型的有效性，在四个标准MILP基准测试中，我们的分支智能体表现优于此前最先进的强化学习方法。
原文摘要 · Abstract (English)
Mixed-Integer Linear Programming (MILP) is a powerful framework used to address a wide range of NP-hard combinatorial optimization problems, often solved by Branch and Bound (B&B). A key factor influencing the performance of B&B solvers is the variable selection heuristic governing branching decisions. Recent contributions have sought to adapt reinforcement learning (RL) algorithms to the B&B setting to learn optimal branching policies, through Markov Decision Processes (MDP) inspired formulations, and ad hoc convergence theorems and algorithms. In this work, we introduce BBMDP, a principled vanilla MDP formulation for variable selection in B&B, allowing to leverage a broad range of RL algorithms for the purpose of learning optimal B\&B heuristics. Computational experiments validate our model empirically, as our branching agent outperforms prior state-of-the-art RL agents on four standard MILP benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。