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

Socpus ID

79955902793 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/79955902793

This document is currently not available here.

Share

COinS