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

Feb, 2021

本研究提出了一种基于神经网络的无数据训练方法，用于解决组合优化问题，特别是最大独立集和最大团的问题，并提出了通用的图缩小过程来处理大规模图形。这种方法在无需数据的情况下，可与有监督学习、强化学习和基于机器学习的现有方法相媲美或更优，具有广泛的适用性。

Mar, 2022

本文介绍了如何使用图神经网络来解决组合优化问题，包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略，我们生成了一个可区分的损失函数，并在无监督训练过程结束后对整数变量进行简单的投影。实验表明，我们的方法在解决包含数百万个变量的问题时能够胜任。

Jul, 2021

本文提出了一种利用神经网络和强化学习解决组合优化问题的框架，特别关注旅行推销员问题和背包问题，证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果，并且可以得到具有多达 200 个项目实例的最优解。

Nov, 2016

本文提出了一种基于无标签示例的图上 CO 问题的无监督学习框架，该框架可以提供具有保证质量的整数解，实现方法为使用神经网络参数化一组概率分布，并基于 Erdos 的概率方法来对其进行优化，最后将解码得到所需的解。该方法在实际数据集和复杂实例上取得了具有竞争力的结果。

Jun, 2020

本文介绍了一种名为 GCOMB 的框架，利用概率贪心机制通过训练图卷积网络 (GCN) 预测一个节点的质量，以此解决图上的组合问题。实验表明，GCOMB 比学术界最先进的组合算法快 100 倍、质量略高。此外，GCOMB 在实际的 Influence Maximization（IM）组合问题上也展现了强大的性能。

Mar, 2019

深度神经网络和强化学习方法在解决复杂的组合问题方面取得了显著的实证成果，本文引入了一种新的理论框架来分析这些方法的有效性，回答了存在生成模型能够生成近似最优解、拥有易处理的参数数量以及优化结果无次优静态点等问题，并介绍了一种新的正则化过程，实验证明其有助于解决梯度消失和避免不良静态点的问题。

Oct, 2023

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

Sep, 2019

本文对神经网络在传统组合优化框架中的性能、可迁移性、计算成本和对更大样本的普适性进行了详细研究，并在 NP-hard 问题线性排序问题上开发了神经组合优化模型。

May, 2022

我们提出了一种利用机器学习技术进行符号计算研究的新方法。我们解释了如何将人类设计的在圆柱代数分解中选择变量顺序的启发式方法表示为受限神经网络。这使我们能够使用机器学习方法进一步优化这个启发式方法，得到与原始人类设计相似复杂度的新网络和新启发式。我们将其作为一种事前可解释性方法用于计算机代数开发。

Apr, 2024