Title

Simulation Of Random Set Covering Problems With Known Optimal Solutions And Correlated Coefficients

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. 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.

Publication Date

12-1-2006

Publication Title

WMSCI 2006 - The 10th World Multi-Conference on Systemics, Cybernetics and Informatics, Jointly with the 12th International Conference on Information Systems Analysis and Synthesis, ISAS 2006 - Proc.

Volume

6

Number of Pages

57-62

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

84867239471 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS