Determining When Gurobi Generates Optimal Solutions for the Partial Coverage Weighted Set Covering Problem

The partial coverage weighted set covering problem (PCWSCP) allows for less than 100% of the rows to be satisfied in a weighted set covering problem (WSCP). This paper does not claim to contribute to operations research (OR) theory or methodology. Instead, it demonstrates that a large number of PCWSCPs based on WSCPs from the OR literature can be efficiently solved using the software Gurobi 12 with default parameter settings on a standard PC. This is an important practical result because it indicates what types of PCWSCPs can be solved optimally using commercial software without resorting to customized algorithms that do not guarantee optimums or even bounds on their solutions. Specifically, using 105 WSCP instances from the literature, 420 PCWSCP instances are generated with 105 instances at 80%, 85%, 90%, and 95% coverage respectively. It is shown that using Gurobi on a standard PC, optimal solutions could be obtained within 300 s (average of 17 s) for instances with up to 800 rows by 8000 columns by 2% density. This is about 86% of the 420 instances. As expected, in general, the execution time decreases as the row coverage decreases. Furthermore, it is shown that initializing (“warm-starting”) Gurobi with solutions from either a greedy, carousel greedy, or local branching algorithm results in no statistically significant difference in performance compared to Gurobi’s cold start. Hence, there is no advantage to “warm-starting” Gurobi with one of these common heuristic approaches when solving PCWSCPs. Finally, this is the first time the weighted version of the partial coverage set covering problem is discussed in the literature. All previous discussions dealt only with solution approaches specifically developed for the unit-cost version of the problem.