Simulating realistic set covering problems with known optimal solutions

    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