Simulation of Random Set Covering Problems with Known Optimal Solutions and Correlated Coefficients

摘要

This paper outlines a methodology to generate random Set Covering Problem (SCP) instances with known optimal solutions and correlated coefficients. It has been established that positive correlation between the objective function coefficients and the column sums of the SCP constraint matrix affects the performance of SCP solution methods. Generating large SCP instances with known optimal solutions and realistic coefficient correlation not only provides an ample opportunity to test the performance of heuristics but also provides a plethora of test problems with controllable problem characteristics, such as correlation. We describe the procedure for generating SCP instances and finally show the results for a pilot study conducted on SCP instances generated by our procedure.