Title
Simulating Realistic Set Covering Problems With Known Optimal Solutions
Keywords
Duality; Explicit correlation induction; Heuristic; Karush-Kuhn-Tucker conditions; Set covering problem
Abstract
This paper outlines a methodology to generate random Set Covering Problem (SCP) instances with known optimal solutions and correlated coefficients. Positive correlation between the objective function coefficients and the column sums of the SCP constraint matrix is known to affect the performance of SCP solution methods. Generating large SCP instances with known optimal solutions and realistic coefficient correlation provides a plethora of test problems with controllable problem characteristics, including correlation, and an ample opportunity to test the performance of SCP heuristics and algorithms without having to solve the problems to optimality. We describe the procedure for generating SCP instances and present the results of a computational demonstration conducted on SCP instances generated by our procedure. This computational demonstration shows that the heuristics' relative errors increase as the correlation increases, that the likelihood of finding a non-optimal solution also increases with the level of correlation, and that the quality of the solutions found is affected by the number of constraints. © 2011 Elsevier Ltd. All rights reserved.
Publication Date
8-1-2011
Publication Title
Computers and Industrial Engineering
Volume
61
Issue
1
Number of Pages
39-47
Document Type
Article
Personal Identifier
scopus
DOI Link
https://doi.org/10.1016/j.cie.2011.02.008
Copyright Status
Unknown
Socpus ID
79955902793 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/79955902793
STARS Citation
Sapkota, Nabin and Reilly, Charles H., "Simulating Realistic Set Covering Problems With Known Optimal Solutions" (2011). Scopus Export 2010-2014. 2659.
https://stars.library.ucf.edu/scopus2010/2659