图上组合优化的统一预训练和适应框架
我们的研究工作的重点是通过决策导向的图学习,在组合优化问题中采用神经网络框架,提出了一个更高效和精确的框架。此外,我们引入了一个决策导向的框架,利用图神经网络解决具有辅助支持的组合优化问题。实验结果表明,我们的方法在经典组合优化问题上优于独立的图神经网络方法和传统方法。
Jun, 2024
图神经网络在解决节点分类、图分类和链接预测等任务方面取得了巨大成功。然而,将图神经网络和机器学习应用于组合优化问题的研究相对较少。本文引入了一种新颖的图神经网络架构,利用复杂的滤波器组和局部化注意机制来解决图上的组合优化问题。我们展示了我们的方法如何与以往基于图神经网络的组合优化求解器区别开来,并在自监督学习设置下有效地应用于最大团、最小支配集和最大割问题。除了证明在各项任务上具有竞争力的整体性能外,我们还为最大割问题建立了最新的研究结果。
May, 2024
本论文提出并证明了图神经网络可以应用于解决组合优化问题,通过将优化过程视为顺序决策问题,使用 Q-Learning 训练图神经网络可以在参数和训练时间上只占一小部分的情况下接近达到最先进的启发式求解器的性能。
Jan, 2024
基于图神经网络 (GNNs) 的统一框架,解决组合优化问题 (COPs),包括 COPs 的图表示、非图结构 COPs 转换为图结构 COPs 的等效转换、图分解和图简化,利用 GNNs 有效捕获关系信息和提取 COPs 图表示的特征,为 COPs 提供了通用解决方案,能够解决非图结构和高度复杂图结构的 COPs 限制。
Jun, 2024
近年来,图神经网络(GNNs)在解决 NP-hard 组合优化问题方面变得越来越流行。本文提出了一种名为 AutoGNP 的新型自动化 GNNs 类别,用于解决 NP-hard 问题,并通过图神经网络搜索算法自动查找给定 NP-hard 组合优化问题的最佳 GNNs,通过实验证明了我们提出模型的优越性。
Jun, 2024
本文提出了一种基于无标签示例的图上 CO 问题的无监督学习框架,该框架可以提供具有保证质量的整数解,实现方法为使用神经网络参数化一组概率分布,并基于 Erdos 的概率方法来对其进行优化,最后将解码得到所需的解。该方法在实际数据集和复杂实例上取得了具有竞争力的结果。
Jun, 2020
本文介绍了如何使用图神经网络来解决组合优化问题,包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略,我们生成了一个可区分的损失函数,并在无监督训练过程结束后对整数变量进行简单的投影。实验表明,我们的方法在解决包含数百万个变量的问题时能够胜任。
Jul, 2021
提出了一种解决组合优化问题的图神经网络体系结构,可运用于所有二元约束满足问题的训练,无监督训练,性能非常优秀。尽管是通用的,但其性能可超过大多数贪心和半定编程算法,有时甚至优于特定问题的最优启发式算法。
Sep, 2019
本文提出第一个对组合优化求解器的实用鲁棒性度量方法,并针对 14 个算法和 CO 问题进行了广泛的实验,在给定时间限制下,发现目前的最先进算法(如 Gurobi)在指定的难例上的性能下降了超过 20%,使人们对组合优化求解器的鲁棒性产生担忧。
Dec, 2021