带时序注意力图神经网络的精确组合优化
本文通过对近年来在组合优化、运筹学和机器学习等领域出现的基于图神经网络(GNNs)的组合优化求解方法和算法进行概述,以此向优化和机器学习研究者介绍这一领域的最新进展。
Feb, 2021
本文提出了一种基于图卷积神经网络的分支定界变量选择新模型,通过模仿学习和强分支专家规则训练,成功解决了组合优化问题。实验结果表明,该方法不仅在分支机制上优于现有的机器学习方法,而且在大问题上也优于现有的专家设计分支规则。
Jun, 2019
本文对神经网络在传统组合优化框架中的性能、可迁移性、计算成本和对更大样本的普适性进行了详细研究,并在 NP-hard 问题线性排序问题上开发了神经组合优化模型。
May, 2022
文章提出一种基于深度学习和启发式算法的图卷积网络方法,用于解决某些 NP 困难问题,并在四个 NP 困难问题和五个数据集上进行了评估,结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平,并具有较强的泛化性和扩展性。
Oct, 2018
本文提出一种名为 Graph Temporal Attention with Reinforcement Learning (GTA-RL) 的新型框架,针对动态组合优化问题学习启发式解决方案。该框架结构包括一个能够嵌入组合问题实例的时间特征的编码器和一个能够动态聚焦于嵌入特征以找到所需组合问题实例的解码器,并针对实时版本组合优化问题进行了扩展。实验证明,与现有方法相比,该方法在动态和实时图组合优化方面具有更高的效率和优化求解器的有效性。
Jan, 2022
本文介绍了如何使用图神经网络来解决组合优化问题,包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略,我们生成了一个可区分的损失函数,并在无监督训练过程结束后对整数变量进行简单的投影。实验表明,我们的方法在解决包含数百万个变量的问题时能够胜任。
Jul, 2021
我们的研究工作的重点是通过决策导向的图学习,在组合优化问题中采用神经网络框架,提出了一个更高效和精确的框架。此外,我们引入了一个决策导向的框架,利用图神经网络解决具有辅助支持的组合优化问题。实验结果表明,我们的方法在经典组合优化问题上优于独立的图神经网络方法和传统方法。
Jun, 2024
介绍了解决图上组合优化问题的现有方法存在的问题,调查了与计算复杂性相关的机器学习研究的发展,并组织和比较了解决组合优化问题的学习结构。
May, 2020
本论文提出并证明了图神经网络可以应用于解决组合优化问题,通过将优化过程视为顺序决策问题,使用 Q-Learning 训练图神经网络可以在参数和训练时间上只占一小部分的情况下接近达到最先进的启发式求解器的性能。
Jan, 2024