<![CDATA[Since 1990, the quality of approximate solution methods for solving weighted set covering problems (WSCPs) has been measured based on how well they solve 65 WSCPs available in Beasley’s OR-Library. In a 2024 paper, it has been shown that guaranteed optimal solutions can easily be obtained for 55 weighted set covering problems (WSCPs) in Beasley’s OR-Library using general-purpose integer programming software. These 55 WSCPs have 500 rows and 5,000 columns or less and were solved in a few seconds on a standard PC. However, the remaining 10 WSCPs have 1000 rows and 10,000 columns and either required considerably more than 1000 seconds to obtain guaranteed optimums (data set NRG) or no optimums were obtained (NRH). The purpose of this short paper is to try to quantify the solution times needed to solve WSCPs using general-purpose integer programming software that are larger than 500 rows and 5,000 columns, but less than 1,000 rows and 10,000 columns. This is important because the size and solution time gap is so large that solution times go from a few seconds for the 55 “smaller” WSCPs to very large solution times for the two largest data sets. To fill this gap, 40 new WSCP instances are defined and their solution times are analyzed to determine when to expect that WSCPs, based on size and density, can be solved to optimality in a timely manner using general-purpose integer programming software like Gurobi or CPLEX.]]>
Copyrights © 2025
