- 使用分支定界进行非线性神经网络验证
本文提出了名为 GenBaB 的通用框架,用于进行神经网络中非线性函数的分支界定与验证,并展示了其在验证各种类型的神经网络以及其他非线性计算图上的有效性。
- 通过机器学习解决一类切割生成线性规划问题
提出了一种基于机器学习的新框架来近似求解割平面问题,并通过分类方法获得近似的割平面,从而提高分支定界树中添加割平面的候选节点的识别效率。
- 运用图指针网络在组合优化中的学习分支
本文提出了一种聚合图神经网络和指针机制的图指针网络模型来学习分支定界中的变量选择策略,结果表明该模型在求解速度和搜索树大小方面都优于现有的机器学习和专家设计的分支规则。
- TreeDQN:学习最小化分枝定界树
本文介绍了一种基于强化学习的组合优化问题解决方法,使用树马尔可夫决策过程视角选择变量分支,并且优化学习对象,相较之前的强化学习方法,训练数据量更小,生成树的大小更小。
- 用新的价值函数进行混合学习解决最大公共子图问题
本研究提出了一种新的基于深度强化学习的顶点选择方法与价值函数,应用于求解最大诱导公共子图问题的分支定界算法,并实验验证了新算法的效果明显优于目前最先进的算法 McSplit+LL 和 McSplit+RL,同时分析证明了新的选择方法和价值函 - 离线排名策略学习在高效混合整数规划中的分支排序
本文提出了一种离线强化学习方法,将分支定界问题的分支决策作为全局决策问题来解决,并通过排名奖励方案将分支方法的长期优势与短期视野进行区分,建立一个离线 MIP 数据集。作者称该方法比现有的基于启发式方法和现有的深度学习方法在优化算法性能方面 - 多神经元松驰引导支配界分支定界的完全验证
提出一种结合多神经元松弛和分支定界 (并运用基于 GPU 的优化器) 的神经网络验证器,将先前的优势综合以解决较大和较有挑战性的网络问题,并在多个基准测试中取得最新的最佳结果。
- 学习剪枝的改进强化学习算法
本文提出了基于深度强化学习的分支定界算法,该算法利用离线模仿学习与自主生成数据相结合的优化方法,并且引入了一种优先存储机制来控制二者之间的混合比例,以此提高算法的性能表现。文章在三个公共研究基准上对所提出的算法进行了评估,并与三种经典的启发 - 基于事件的运动估计的全局最优对比度最大化
利用分支定界法提出基于对比度最大化的事件流运动估计算法,将其应用于视频稳定和姿态估计等实际应用中,获得全局优化解决方案,且具有较高的运算速度和精度。
- 分支定界用于分段线性神经网络验证
研究了深度学习的形式验证以及提出了一种基于分支定界的族算法,并提出了新型的组合方法,以及新的有效的分支策略,将之用于高维输入上的问题,并提出包含以前发布的测试案例的全面测试数据集和基准测试。
- 使用图卷积神经网络进行精确组合优化
本文提出了一种基于图卷积神经网络的分支定界变量选择新模型,通过模仿学习和强分支专家规则训练,成功解决了组合优化问题。实验结果表明,该方法不仅在分支机制上优于现有的机器学习方法,而且在大问题上也优于现有的专家设计分支规则。
- IJCAI基于学习的分支定界算法求解最大公共子图问题
本文提出了一种受强化学习启发式的分枝策略,旨在尽早到达树叶以大大减小搜索树的大小,对于解决典型的最大公共子图(MCS)问题的分枝限界算法具有显著的效果优势。
- 割平面选择中的理论挑战
对比不同种类的切割平面以及它们间的相对强度,讨论在分支定界树中选取一个投资组合的切割平面的问题,提出一些新的方法。在研究中,试图为切割平面选择设计出一种更为系统的方法。同时我们为与切割平面选择有关的一些问题提供了初步的理论基础。
- 用于同时相机位姿和特征对应的全局优化局内点集最大化
应用全局最优内点集基数最大化方法求解相机位姿和对应特征点,使用 SE (3) 几何学方法来限定内点上下界限,并利用分支定界算法在 6 维相机位姿空间进行搜索,实验结果表明该方法更加鲁棒可靠,并表现出比使用局部最优化方法更好的速度和精度。
- ICML树独立的双树算法
该研究介绍了一种四部分逻辑划分和一个元算法,可以使得经典的双树算法具有可移植性且易于拓展到新类型的树,其中包含了 k 最近邻搜索算法以及一个新的紧密剪枝方法,同时在大规模并行场景下也可以轻松拓展。
- KDD使用树形数据结构进行最大内积搜索
本文提出了针对内积最优匹配问题的新型分支边界算法,包括使用树形结构的一般分支边界算法、针对多个查询的双树算法以及新型数据结构等,实验结果表明与朴素搜索技术相比,该算法能使查询时间提升高达 5 个数量级。
- 非对称旅行商问题的相变和骨架
本文研究了 ATSP 中的相变现象,发现随着城市间距离精度的提高,问题的最优解成本和计算成本都会出现急剧的变化。这些结果有助于更好地生成 ATSP 问题实例。