add to favorites : reference url back to results : previous : next
 

SIMULATION OF RANDOM SET COVERING PROBLEMS WITH KNOWN OPTIMAL SOLUTIONS AND EXPLICITLY INDUCED CORRELATIONS AMOONG COEFFICIENTS
Access this item.
TitleSIMULATION OF RANDOM SET COVERING PROBLEMS WITH KNOWN OPTIMAL SOLUTIONS AND EXPLICITLY INDUCED CORRELATIONS AMOONG COEFFICIENTS
AuthorSapkota, Nabin
KeywordsCorrelated coefficients
set covering
column generation
random problem generation
AbstractThe objective of this research is to devise a procedure to generate random Set Covering Problem (SCP) instances with known optimal solutions and correlated coefficients. The procedure presented in this work can generate a virtually unlimited number of SCP instances with known optimal solutions and realistic characteristics, thereby facilitating testing of the performance of SCP heuristics and algorithms. A four-phase procedure based on the Karush-Kuhn-Tucker (KKT) conditions is proposed to generate SCP instances with known optimal solutions and correlated coefficients. Given randomly generated values for the objective function coefficients and the sum of the binary constraint coefficients for each variable and a randomly selected optimal solution, the procedure: (1) calculates the range for the number of possible constraints, (2) generates constraint coefficients for the variables with value one in the optimal solution, (3) assigns values to the dual variables, and (4) generates constraint coefficients for variables with value 0 in the optimal solution so that the KKT conditions are satisfied. A computational demonstration of the procedure is provided. A total of 525 SCP instances are simulated under seven correlation levels and three levels for the number of constraints. Each of these instances is solved using three simple heuristic procedures. The performance of the heuristics on the SCP instances generated is summarized and analyzed. The performance of the heuristics generally worsens as the expected correlation between the coefficients increases and as the number of constraints increases. The results provide strong evidence of the benefits of the procedure for generating SCP instances with correlated coefficients, and in particular SCP instances with known optimal solutions.
AdviserReilly, Charles
PublisherUniversity of Central Florida
DegreePh.D.
Degree DisciplineDepartment of Industrial Engineering and Management Systems
Degree GrantorEngineering and Computer Science
Degree ProgramIndustrial Engineering and Management Systems
Graduation Date2006-12-01
TypeDoctoral dissertation
Access LevelPublic - Allow Worldwide Access
Release Date2008-01-01
RepositoryUniversity Archives
Repository CollectionElectronic Theses and Dissertations
IdentifierCFE0001416
Access Linkhttp://purl.fcla.edu/fcla/etd/CFE0001416

add to favorites : reference url back to results : previous : next
powered by CONTENTdm ® | contact us  ^ to top ^