Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks
This addresses combinatorial optimization for researchers and practitioners by providing a faster alternative to commercial solvers without compromising quality, though it is incremental as it augments existing methods.
The paper tackles accelerating the Set Cover Problem (SCP) by proposing Graph-SCP, a graph neural network method that reduces problem size by 60-80% and achieves up to 10x runtime speedups compared to Gurobi while maintaining solution quality.
Machine learning (ML) approaches are increasingly being used to accelerate combinatorial optimization (CO) problems. We investigate the Set Cover Problem (SCP) and propose Graph-SCP, a graph neural network method that augments existing optimization solvers by learning to identify a smaller sub-problem that contains the solution space. Graph-SCP uses both supervised learning from prior solved instances and unsupervised learning to minimize the SCP objective. We evaluate the performance of Graph-SCP on synthetically 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 60-80% and achieves runtime speedups of up to 10x on average when compared to Gurobi (a state-of-the-art commercial solver), while maintaining solution quality. This is in contrast to fast greedy solutions that significantly compromise solution quality to achieve guaranteed polynomial runtime. We showcase Graph-SCP's ability to generalize to larger problem sizes, training on SCP instances with up to 3,000 subsets and testing on SCP instances with up to 10,000 subsets.