使用无数据神经网络的可微组合优化方法

Mar, 2022

使用无数据神经网络的可微组合优化方法

A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks

Ismail R. Alkhouri, George K. Atia, Alvaro Velasquez

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

Abstract

The success of machine learning solutions for reasoning about discrete structures has brought attention to its adoption within combinatorial optimization algorithms. Such approaches generally rely on supervised learning by leveraging datasets of the combinatorial structures of interest drawn from some distribution of problem instances. Reinforcement learning

combinatorial optimization neural networks dataless training scheme maximum independent sets maximum cliques

发现论文，激发创造

最大独立集问题的无数据二次神经网络

通过引入一种新颖的无数据二次神经网络，该论文解决了最大独立集问题，并展示了与现有学习方法相比具有竞争力或更好性能的优势。

Jun, 2024

物理启发图神经网络的组合优化

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

Jul, 2021

组合优化中的细粒度搜索空间剪枝和启发式学习

该研究提出了一种基于机器学习的框架来扩大组合优化算法，并使用可解释的学习模型来提供更深层次的洞见，以设计更好的启发式方法，在最大团枚举问题中展示了该框架的性能，并从中获得启示设计了一种新的启发式方法。

Jan, 2020

基于图神经网络的组合优化和推理

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

Feb, 2021

Erdos Goes Neural: 图形组合优化的无监督学习框架

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

Jun, 2020

现代图神经网络在解决诸如最大独立集等组合优化问题方面表现不如传统的贪心算法

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

Jun, 2022

最大约束满足的图神经网络

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

Sep, 2019

深度学习在组合优化树搜索中的问题

本研究提出了一个开源基准套件，对最大独立集问题进行了深入分析，结果表明现有的机器学习算法未能学习最优解的结构，算法技术仍是获得有效解决方案的关键。

Jan, 2022

神经组合优化：领域的新玩家

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

May, 2022

图形 Q-Learning 用于组合优化

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

Jan, 2024