Nov, 2022

带障碍的分支定界：用于基于 DD 的分支定界的支配与次优解检测

PDF
TL;DR本论文介绍了一种基于决策图的分支定界算法，利用动态规划模型的结构以及数据结构 Barrier 中的阈值进行剪枝，进而解决优化问题，并结合 Gillard 等人在 2021 年提出的过滤技术进行优化，实验结果表明该方法能够在更短的时间内解决更难的优化问题。
发现论文，激发创造
  • 分支：用于优化决策树的快速动态规划和分支限界算法

    Branches 算法结合了动态规划和分支界限方法，提供了出色的速度和稀疏性解决方案，通过理论分析和实证评估验证了比现有方法更低复杂性以及始终产生最优的决策树的优势。

    Jun, 2024

  • MORBDD：多目标受限二进制决策图的稀疏学习

    通过机器学习方法，本研究使用二进制决策图在多准则决策中精确求解多目标整数线性规划问题，发现适用于单目标问题的局限二进制决策图可通过 ML 方法进行改进，产生具有优秀近似精度且规模较小的稀疏解。

    Mar, 2024

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

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

    Jun, 2023

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

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

    Jan, 2022

  • 通过 Lagrangian 分解改进的神经网络验证分支定界算法

    本篇论文提出了基于 Lagrangian Decomposition 的 bounding 算法和一种新的基于 activation 的 branching 策略。这些新方法应用于 BaDNB 框架中，比以前的完整验证系统具有更快的效率和更高的可扩展性。

    Apr, 2021

  • 利用机器学习提高优化范围：决策图遇上深度强化学习

    本文提出一种基于深度强化学习的通用方法，用于优化决策图的变量排序以获得更紧密的上下界，进而直接通过泛化的边界机制提高组合优化问题的解决效率。 在两个具体应用中，作者证明了该方法能够显著提高上下界的效果。

    Sep, 2018

  • 基于学习的分支定界算法求解最大公共子图问题

    本文提出了一种受强化学习启发式的分枝策略，旨在尽早到达树叶以大大减小搜索树的大小，对于解决典型的最大公共子图（MCS）问题的分枝限界算法具有显著的效果优势。

    May, 2019

  • 一种通用的一阶算法框架，用于双层规划，超越了下层单例

    提出了 Bi-level Descent Aggregation (BDA) 算法框架，能够解决通用的双层优化问题且不需要 Lower-Level Singleton (LLS) 条件，并进一步改进了传统 LLS 方法的收敛性。实验结果证明了该算法在超参数优化和元学习等任务上的卓越性能。

    Jun, 2020

  • 一个新的分支界限修剪框架用于 $l_0$ 正则化问题

    通过分支定界（Branch-and-Bound）算法解决涉及 $\ell_0$ 正则化的学习问题，并提出一种用于一类通用的 $\ell_0$ 正则化问题的修剪测试的替代方法，该方法可以同时评估多个区域，在标准分支定界实现中具有可忽略的计算开销，并通过数值模拟表明该修剪策略可以将分支定界过程的求解时间从机器学习应用中常见的典型问题的数量级上提升。

    Jun, 2024

  • 学习分支

    使用机器学习确定任何一组划分程序的最佳加权，并通过实验证明，学习如何分叉在实践中非常有益，可以显著减小树的规模。

    Mar, 2018