A GPU-based Method for Finding Optimal Solution to the Set Covering Problem

The computation time of the exact and optimal solution to the set covering problem increases exponentially concerning the problem size due to an exhaustive search for the solution. We propose a novel GPU-based parallel method that is successful enough to accelerate the computation of the optimal solution via the exact exhaustive algorithm. This method shows significant SpeedUp in the computation of the optimal solution of the set covering problem with respect to the sequential method.