本文通过对近年来在组合优化、运筹学和机器学习等领域出现的基于图神经网络（GNNs）的组合优化求解方法和算法进行概述，以此向优化和机器学习研究者介绍这一领域的最新进展。

Feb, 2021

该论文引入了一种物理启发的无监督图神经网络以解决稀疏图上的组合优化问题，作者展示了在最大割和最大独立集问题上这些 GNNs 的性能可以与或优于现有求解器，并且具有处理百万变量问题的能力。然而，该评论提出了一个简单贪心算法可以找到比 GNN 更好的质量的解决方案。此外，该评论者还建议通过基于真正困难的问题的标准基准测试未来的神经网络优化器。

Jun, 2022

提出了一种解决组合优化问题的图神经网络体系结构，可运用于所有二元约束满足问题的训练，无监督训练，性能非常优秀。尽管是通用的，但其性能可超过大多数贪心和半定编程算法，有时甚至优于特定问题的最优启发式算法。

Sep, 2019

我们的研究工作的重点是通过决策导向的图学习，在组合优化问题中采用神经网络框架，提出了一个更高效和精确的框架。此外，我们引入了一个决策导向的框架，利用图神经网络解决具有辅助支持的组合优化问题。实验结果表明，我们的方法在经典组合优化问题上优于独立的图神经网络方法和传统方法。

Jun, 2024

近年来，图神经网络（GNNs）在解决 NP-hard 组合优化问题方面变得越来越流行。本文提出了一种名为 AutoGNP 的新型自动化 GNNs 类别，用于解决 NP-hard 问题，并通过图神经网络搜索算法自动查找给定 NP-hard 组合优化问题的最佳 GNNs，通过实验证明了我们提出模型的优越性。

Jun, 2024

本论文提出并证明了图神经网络可以应用于解决组合优化问题，通过将优化过程视为顺序决策问题，使用 Q-Learning 训练图神经网络可以在参数和训练时间上只占一小部分的情况下接近达到最先进的启发式求解器的性能。

Jan, 2024

文章提出一种基于深度学习和启发式算法的图卷积网络方法，用于解决某些 NP 困难问题，并在四个 NP 困难问题和五个数据集上进行了评估，结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平，并具有较强的泛化性和扩展性。

Oct, 2018

我们设计了图神经网络架构，利用半定规划的强大算法工具，来获得一类组合优化问题的最优逼近算法。通过研究，我们证明了多项式大小的消息传递算法可以表示 Max Constraint Satisfaction Problems 的最强多项式时间算法（基于 Unique Games Conjecture）。我们利用这一结果构建了高效的图神经网络架构 OptGNN，在最大割和最大独立集等经典组合优化问题上获得了高质量的近似解。我们的方法在各种真实和合成数据集上取得了强有力的实证结果，超过了神经基准和传统算法。最后，我们利用 OptGNN 捕捉凸松弛的能力，设计了一个从 OptGNN 学习的嵌入中产生对优解的对偶证明的算法。

Oct, 2023

本文提出了一种基于图卷积神经网络的分支定界变量选择新模型，通过模仿学习和强分支专家规则训练，成功解决了组合优化问题。实验结果表明，该方法不仅在分支机制上优于现有的机器学习方法，而且在大问题上也优于现有的专家设计分支规则。

Jun, 2019

Schuetz 等人提出了一种使用图神经网络作为启发式方法来解决各种组合优化问题的方案，该方法通过样例实例对网络进行训练，并应用广泛使用的技术来评估其成功的能力，尽管报告的结果只比梯度下降略有改善，但该方法承诺具有高度可伸缩性和计算成本线性。

Oct, 2022