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

Jun, 2022

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

Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch

Tianyu Zhang, Amin Banitalebi-Dehkordi, Yong Zhang

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

Abstract

Branch-and-bound is a systematic enumerative method for combinatorial optimization, where the performance highly relies on the variable selection strategy. State-of-the-art handcrafted heuristic strategies suffer from relatively slow inference time for each selection, while the current

combinatorial optimization reinforcement learning variable selection monte-carlo tree search machine learning

发现论文，激发创造

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

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

Jan, 2022

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

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

Jun, 2023

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

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

May, 2020

结合强化学习和约束编程用于组合优化

本文介绍了一种基于深度强化学习和约束编程的混合算法，应用于复杂的组合优化问题，并在实验中成功运用于旅行商问题和投资组合优化问题，表现优于单独的深度强化学习和约束编程算法，同时也达到了与工业级求解器相竞争的水平。

Jun, 2020

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

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

May, 2022

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

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

Sep, 2023

强化学习的组合探索优化

在解决复杂优化问题方面，探索式组合优化（ECO-DQN）通过连续改进解决方案，从而有效地学习有效的启发式方法来解决图上的组合优化问题，并在最大割问题上展示了最先进的强化学习性能。

Sep, 2019

使用强化学习的受限组合优化

本文提出一个深度强化学习的框架来解决受限的组合优化问题，将受约束的组合问题定义为完全可观的受约束马尔可夫决策过程（CMDP），并提出从不满足的约束产生惩罚信号，以推断作为启发式算法的策略。通过对约束工厂和资源分配问题进行的实验表明，本文的提议对于比较经典的启发式算法、元启发式算法和约束编程（CP）求解器来说，能更快地求得答案。

Jun, 2020

运用图指针网络在组合优化中的学习分支

本文提出了一种聚合图神经网络和指针机制的图指针网络模型来学习分支定界中的变量选择策略，结果表明该模型在求解速度和搜索树大小方面都优于现有的机器学习和专家设计的分支规则。

Jul, 2023

组合优化的强化学习：一项调查研究

本文综述了近期在强化学习领域中在解决组合优化问题方面的进展，包含了 RL 框架与传统算法的比较以及各方法解决不同问题的时间线，结果表明基于 RL 的模型成为解决组合问题的方向值得期待。

Mar, 2020