HypOp: Distributed Constrained Combinatorial Optimization leveraging Hypergraph Neural Networks

可扩展地寻址高维受限组合优化问题是几个科学和工程学科中面临的挑战。最近的研究引入了图神经网络来解决多项式成本的无约束组合优化问题。本文提出了一个名为HypOp的新框架，它在解决组合优化问题方面在几个方面大大提高了现有技术水平：(i)它将先前的结果推广到具有任意成本函数的约束优化问题上；(ii)它通过利用超图神经网络结构将应用扩展到更高维的问题；(iii)它通过引入用于超图神经网络训练的新分布式和并行架构，使可扩展性达到更大的问题；(iv)它通过从解决一个成本/约束集合的学习经验中进行知识转移，展示了对其他问题公式的泛化能力；(v)与先前的技术相比，通过使用模拟退火提出微调步骤，显著提高了解决方案的准确性；(vi) HypOp在基准示例上取得了显着进展，通过组合微调和分布式训练技术，运行时间提高了多达五倍。该框架允许解决一系列新的科学问题，包括超图最大割问题，可满足性问题（3SAT）和资源分配。我们通过解决NDC药物物质超图上的超图最大割问题展示了HypOp在科学发现中的应用。通过在各种组合优化问题上进行广泛的实验，HypOp展示了优于现有的无监督学习基础求解器和通用优化方法。

本文旨在解决高维度约束组合优化问题的可扩展寻址挑战，提出了一种名为HypOp的新框架，以解决多个科学和工程领域中的组合优化问题。

HypOp框架通过引入超图神经网络结构，将先前的结果推广到具有任意成本函数的约束优化问题，并通过引入新的分布式和并行架构来实现可扩展性。

HypOp框架通过fine-tuning和分布式训练技术的组合，将运行时间提高了多达五倍，并在多个组合优化问题上展示了卓越的性能。实验使用了多个数据集，展示了HypOp在科学发现中的应用，同时还提供了开源代码。

最近的相关研究包括利用图神经网络解决组合优化问题的工作，如Graph Convolutional Networks for Combinatorial Optimization: A Review等。