Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring the fact that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning, especially graph neural networks (GNNs), as a key building block for combinatorial tasks, either as solvers or as helper functions. GNNs are an inductive bias that effectively encodes combinatorial and relational input due to their permutation-invariance and sparsity awareness. This paper presents a conceptual review of recent key advancements in this emerging field, aiming at both the optimization and machine learning researcher.
翻译:组合优化是业务研究和计算机科学中一个公认的领域,直到最近,其方法一直侧重于孤立地解决问题,忽视了通常产生于实际中相关数据分布的事实,然而,近年来,人们对使用机器学习,特别是图形神经网络(GNN)作为组合任务的关键构件的兴趣激增,无论是作为解决者还是作为辅助者。 GNN是一种诱导偏差,有效地编码了组合和关联输入,因为它们的变异性与孔隙意识。本文对这个新兴领域最近的关键进展进行了概念性审查,目的是优化和机器学习研究者。