Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks
Zohair Shafi Benjamin A. Miller Tina Eliassi-Rad Rajmonda S. Caceres
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.