Title

Simulating realistic set covering problems with known optimal solutions

Authors

Authors

N. Sapkota;C. H. Reilly

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Comput. Ind. Eng.

Keywords

Set covering problem; Explicit correlation induction; Karush-Kuhn-Tucker; conditions; Duality; Heuristic; 0-1 KNAPSACK-PROBLEM; ALGORITHMS; GENERATION; SYSTEM; BOUNDS; Computer Science, Interdisciplinary Applications; Engineering, ; Industrial

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. Published by Elsevier Ltd.

Journal Title

Computers & Industrial Engineering

Volume

61

Issue/Number

1

Publication Date

1-1-2011

Document Type

Article

Language

English

First Page

39

Last Page

47

WOS Identifier

WOS:000291458300004

ISSN

0360-8352

Share

COinS