Machine learning (ML) approaches are increasingly being used to accelerate combinatorial optimization (CO) problems. We look specifically at the Set Cover Problem (SCP) and propose Graph-SCP, a graph neural network method that can augment existing optimization solvers by learning to identify a much smaller sub-problem that contains the solution space. We evaluate the performance of Graph-SCP on synthetic weighted and unweighted SCP instances with diverse problem characteristics and complexities, and on instances from the OR Library, a canonical benchmark for SCP. We show that Graph-SCP reduces the problem size by 30-70% and achieves run time speedups up to~25x when compared to commercial solvers (Gurobi). Given a desired optimality threshold, Graph-SCP will improve upon it or even achieve 100% optimality. This is in contrast to fast greedy solutions that significantly compromise solution quality to achieve guaranteed polynomial run time. Graph-SCP can generalize to larger problem sizes and can be used with other conventional or ML-augmented CO solvers to lead to potential additional run time improvement.

使用机器学习方法来加速组合优化问题，具体研究了集合覆盖问题，并提出了图神经网络方法 Graph-SCP，通过学习识别包含解空间的较小子问题来增强现有优化求解器，实验结果表明，Graph-SCP 与商业求解器相比可将问题规模减少 30-70%，运行时间加速高达 25 倍，并能够达到或甚至优于给定最优性阈值，相比快速贪心解法，Graph-SCP 在保持高质量解的同时实现多项式运行时间保证，可推广到更大的问题，并与其他传统或机器学习增强的组合优化求解器结合使用以进一步提高运行时间。

图神经网络加速集合覆盖问题