面向基于学习的方法的组合问题的通用表示
本文通过对近年来在组合优化、运筹学和机器学习等领域出现的基于图神经网络(GNNs)的组合优化求解方法和算法进行概述,以此向优化和机器学习研究者介绍这一领域的最新进展。
Feb, 2021
介绍了解决图上组合优化问题的现有方法存在的问题,调查了与计算复杂性相关的机器学习研究的发展,并组织和比较了解决组合优化问题的学习结构。
May, 2020
本文研究如何将深度强化学习和图神经网络应用于无线网络中的电力和信道分配问题,研究结果表明现有结构还不能很好地识别图的结构和特征,并且对于对图产生影响的问题不太适用,但研究还是取得了一些积极进展,比如通过距离编码来增强问题的表示方法。
Jan, 2022
介绍了一种广泛适用的形式主义,即组合问题图,以解决机器学习中不利于推广的问题,提出了组合泛化问题并引入组合递归学习器,该框架适用于学习算法过程以组合表示转换,从而产生能够进行推理的学习器。
Jul, 2018
本文提出了一种基于图卷积神经网络的分支定界变量选择新模型,通过模仿学习和强分支专家规则训练,成功解决了组合优化问题。实验结果表明,该方法不仅在分支机制上优于现有的机器学习方法,而且在大问题上也优于现有的专家设计分支规则。
Jun, 2019
提出了一种解决组合优化问题的图神经网络体系结构,可运用于所有二元约束满足问题的训练,无监督训练,性能非常优秀。尽管是通用的,但其性能可超过大多数贪心和半定编程算法,有时甚至优于特定问题的最优启发式算法。
Sep, 2019
本论文提出并证明了图神经网络可以应用于解决组合优化问题,通过将优化过程视为顺序决策问题,使用 Q-Learning 训练图神经网络可以在参数和训练时间上只占一小部分的情况下接近达到最先进的启发式求解器的性能。
Jan, 2024
设计了一种名为 COMBHelper 的神经方法,借助图神经网络(GNN)识别有前景的节点,压缩搜索空间并提高传统组合优化算法的效率;包括知识蒸馏模块和问题特定增强模块以进一步提升效果,实验证明传统算法利用 COMBHelper 至少快于原始版本 2 倍。
Dec, 2023
本文介绍了如何使用图神经网络来解决组合优化问题,包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略,我们生成了一个可区分的损失函数,并在无监督训练过程结束后对整数变量进行简单的投影。实验表明,我们的方法在解决包含数百万个变量的问题时能够胜任。
Jul, 2021
本文介绍一种将组合优化算法和深度学习相结合的方法,利用神经网络中的组合构建块来解决原始输入数据中的组合问题,如机器人中的路线规划和多目标跟踪中的全局一致性保证。作者将 Gurobi MIP 求解器、Blossom V 算法和 Dijkstra 算法引入到结构中,实现了高效的反向传递,为旅行商问题,最小成本完美匹配问题和最短路径问题提供了特征提取方案。
Dec, 2019