利用回溯轨迹的强化学习在分支定界优化中的应用

AAAIMay, 2022

利用回溯轨迹的强化学习在分支定界优化中的应用

Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories

Christopher W. F. Parsonson, Alexandre Laterre, Thomas D. Barrett

TL;DR本文提出一种名为 retro branching 的强化学习方法，用于解决混合整数线性规划问题中的 branch-and-bound 算法中的变量选择问题，与之前的方法相比，本方法不需要专家指导或预训练，且在四种组合问题上表现优异。

Abstract

combinatorial optimisation problems framed as mixed integer linear programmes (MILPs) are ubiquitous across a range of real-world applications. The canonical branch-and-bound algorithm seeks to exactly solve MILP

combinatorial optimisation mixed integer linear programmes machine learning reinforcement learning branching

发现论文，激发创造

学习剪枝的改进强化学习算法

本文提出了基于深度强化学习的分支定界算法，该算法利用离线模仿学习与自主生成数据相结合的优化方法，并且引入了一种优先存储机制来控制二者之间的混合比例，以此提高算法的性能表现。文章在三个公共研究基准上对所提出的算法进行了评估，并与三种经典的启发式方法以及一种先进的模仿学习算法进行了比较。研究结果表明，所提出的算法在性能上表现最佳，并具有不断提高分支定界算法性能的潜力。

Jan, 2022

使用 Tree MDPs 进行分支学习

本文通过强化学习的方法，提出了树马尔科夫决策过程的概念，从头学习分支规则，并通过计算实验证明了树马尔科夫决策过程对于 MILP 中学习分支问题具有更好的收敛性能。

May, 2022

分支定界算法中的变量选择强化学习

文章提出了一种名为 FMSTS 的新型增强学习方法，采用一种全新的分支策略来优化整数线性规划问题，具有一致性和泛化能力，并在计算实验中验证了其有效性。

May, 2020

精确组合优化的深度强化学习：学习分支

本文提出一种基于强化学习的方法用于解决组合优化中的数据标记和推理延迟问题，并使用蒙特卡罗树搜索和价值网络提高策略网络的性能表现。作者在四种不同类别的组合优化问题上进行了评估，结果表明该方法相较于现有机器学习和启发式方法有更优的性能表现。

Jun, 2022

TreeDQN：学习最小化分枝定界树

本文介绍了一种基于强化学习的组合优化问题解决方法，使用树马尔可夫决策过程视角选择变量分支，并且优化学习对象，相较之前的强化学习方法，训练数据量更小，生成树的大小更小。

Jun, 2023

离线排名策略学习在高效混合整数规划中的分支排序

本文提出了一种离线强化学习方法，将分支定界问题的分支决策作为全局决策问题来解决，并通过排名奖励方案将分支方法的长期优势与短期视野进行区分，建立一个离线 MIP 数据集。作者称该方法比现有的基于启发式方法和现有的深度学习方法在优化算法性能方面更有效。

Jul, 2022

机器学习增强的混合整数线性规划的支配分枝

混合整数线性规划 (MILP) 是数学优化领域的重要组成部分，其提供了一个强大的建模语言，适用于各种应用领域。本文总结了近年来在 MILP 求解中使用机器学习算法优化分支定界等主要任务的发展，探索了机器学习和数学优化的整合以及其对 MILP 求解效果的提升。

Feb, 2024

CAMBranch：使用增强型 MILP 进行区分学习的分支

通过引入机器学习框架加强了解决混合整数线性规划（MILP）的分支策略，特别是通过模仿学习强分支方法，提出了一种新的框架 CAMBranch，借助变量转移生成增强 MILPs（AMILPs），并利用对比学习提高模型的能力从而改善分支决策质量。

Feb, 2024

支持向量机中节点选择的强化学习

使用一种新颖的双模拟技术，通过强化学习模型从整个树状态中选择节点，借助图神经网络生成基于路径的概率分布，将节点选择建模为概率分布，训练模型以实现高质量的节点选择策略，并在严格时间约束下，在多个基准测试中显示出显著的性能改进。

Sep, 2023

强化学习中基于反馈的树搜索

本文提出一种基于模型的强化学习技术，该技术将 Monte-Carlo 树搜索应用于无限期 Marov 决策过程的有限期版本，并使用值函数和策略函数的组合来规定有限期问题的终端条件或决策树的叶节点评估器。作者还提供了第一个基于树搜索的强化学习算法的样本复杂度边界，并证明由深度神经网络实现的技术能够创建一种竞争性人工智能代理。

May, 2018