用强化学习提升分支定界法效率,通过历史轨迹复现改进决策智能。
ReviBranch: Deep Reinforcement Learning for Branch-and-Bound with Revived Trajectories
- 构建搜索树中变量选择与状态的显式历史对应,捕捉结构演化与时间依赖。
- 引入重要性加权奖励重分配,将稀疏奖励转化为密集反馈,提升训练效果。
- 在大规模问题上减少4.0%节点、2.2%单纯形迭代,泛化能力强,适合复杂优化场景。
分支定界(B&B)是求解混合整数线性规划(MILP)的主要方法,其中分支变量的选择直接影响计算效率。传统启发式方法难以在异构问题实例间泛化,而现有基于学习的方法如模仿学习(IL)依赖专家示范质量,强化学习(RL)则面临奖励稀疏与状态表示动态变化的挑战。为此,我们提出ReviBranch,一种新型深度强化学习框架,通过复现搜索树路径中分支决策与图状态间的显式历史对应关系,构建复兴轨迹。训练过程中,该框架使智能体能够学习分支过程中的完整结构演化与时间依赖关系。此外,我们设计了一种重要性加权奖励重分配机制,将稀疏的终端奖励转化为密集的步骤反馈,缓解奖励稀疏问题。在多个MILP基准测试上的实验表明,ReviBranch优于当前最优的RL方法,在大规模实例上分别减少4.0%的B&B节点和2.2%的单纯形迭代次数,展现出对异构MILP问题类的鲁棒性与泛化能力。
原文摘要 · Abstract (English)
The Branch-and-bound (B&B) algorithm is the main solver for Mixed Integer Linear Programs (MILPs), where the selection of branching variable is essential to computational efficiency. However, traditional heuristics for branching often fail to generalize across heterogeneous problem instances, while existing learning-based methods such as imitation learning (IL) suffers from dependence on expert demonstration quality, and reinforcement learning (RL) struggles with limitations in sparse rewards and dynamic state representation challenges. To address these issues, we propose ReviBranch, a novel deep RL framework that constructs revived trajectories by reviving explicit historical correspondences between branching decisions and their corresponding graph states along search-tree paths. During training, ReviBranch enables agents to learn from complete structural evolution and temporal dependencies within the branching process. Additionally, we introduce an importance-weighted reward redistribution mechanism that transforms sparse terminal rewards into dense stepwise feedback, addressing the sparse reward challenge. Extensive experiments on different MILP benchmarks demonstrate that ReviBranch outperforms state-of-the-art RL methods, reducing B&B nodes by 4.0% and LP iterations by 2.2% on large-scale instances. The results highlight the robustness and generalizability of ReviBranch across heterogeneous MILP problem classes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。