使用机器学习确定任何一组划分程序的最佳加权,并通过实验证明,学习如何分叉在实践中非常有益,可以显著减小树的规模。
Mar, 2018
本文提出了一种基于图卷积神经网络的分支定界变量选择新模型,通过模仿学习和强分支专家规则训练,成功解决了组合优化问题。实验结果表明,该方法不仅在分支机制上优于现有的机器学习方法,而且在大问题上也优于现有的专家设计分支规则。
Jun, 2019
文章提出了一种名为FMSTS的新型增强学习方法,采用一种全新的分支策略来优化整数线性规划问题,具有一致性和泛化能力,并在计算实验中验证了其有效性。
May, 2020
本文提出了基于深度强化学习的分支定界算法,该算法利用离线模仿学习与自主生成数据相结合的优化方法,并且引入了一种优先存储机制来控制二者之间的混合比例,以此提高算法的性能表现。文章在三个公共研究基准上对所提出的算法进行了评估,并与三种经典的启发式方法以及一种先进的模仿学习算法进行了比较。研究结果表明,所提出的算法在性能上表现最佳,并具有不断提高分支定界算法性能的潜力。
Jan, 2022
本文通过强化学习的方法,提出了树马尔科夫决策过程的概念,从头学习分支规则,并通过计算实验证明了树马尔科夫决策过程对于MILP中学习分支问题具有更好的收敛性能。
May, 2022
本文提出一种名为 retro branching 的强化学习方法,用于解决混合整数线性规划问题中的 branch-and-bound 算法中的变量选择问题,与之前的方法相比,本方法不需要专家指导或预训练,且在四种组合问题上表现优异。
本文提出了一种离线强化学习方法,将分支定界问题的分支决策作为全局决策问题来解决,并通过排名奖励方案将分支方法的长期优势与短期视野进行区分,建立一个离线MIP数据集。作者称该方法比现有的基于启发式方法和现有的深度学习方法在优化算法性能方面更有效。
Jul, 2022
本文介绍了一种基于强化学习的组合优化问题解决方法,使用树马尔可夫决策过程视角选择变量分支,并且优化学习对象,相较之前的强化学习方法,训练数据量更小,生成树的大小更小。
Jun, 2023
通过引入机器学习框架加强了解决混合整数线性规划(MILP)的分支策略,特别是通过模仿学习强分支方法,提出了一种新的框架CAMBranch,借助变量转移生成增强MILPs(AMILPs),并利用对比学习提高模型的能力从而改善分支决策质量。
Feb, 2024
混合整数线性规划 (MILP) 是数学优化领域的重要组成部分,其提供了一个强大的建模语言,适用于各种应用领域。本文总结了近年来在 MILP 求解中使用机器学习算法优化分支定界等主要任务的发展,探索了机器学习和数学优化的整合以及其对 MILP 求解效果的提升。