A Simple Hybrid Approach for Solving Set Covering Problems with Conflict Constraints

The classic set covering problem (SCP) is an NP-hard binary integer optimization problem with diverse business and industrial applications. Its primary goal is to consolidate resources by selecting a minimal cost subset of columns in a matrix that covers all required rows. Traditionally, conflicts between selected resources were resolved after generating a solution, often adding managerial effort and inefficiency. Recently, two papers have tried to handle conflict constraints explicitly as part of the SCP solution generation process. This paper focuses on SCPs with soft conflict constraints (SCP-SCC), where violations are allowed but with penalties, and proposes a simple hybrid solution approach that combines a GRASP-based heuristic with Gurobi optimization. Using 360 test instances (160 from the literature and 200 new instances), this hybrid approach results in a 7.4% performance improvement over Gurobi, demonstrating the benefit of integrating heuristic and exact solution methods. In addition, classification tree analysis is applied as an attempt to identify problem features (such as conflict graph density and size) that can be used to predict when SCP-SCC instances will likely be difficult to solve to proven optimality efficiently using Gurobi. These insights provide practical guidance for operations research practitioners, enabling informed decisions among heuristic, exact, or hybrid solution approaches and improving efficiency in real-world applications.