The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance
Raymond R. Hill () and
Charles H. Reilly ()
Additional contact information
Raymond R. Hill: Air Force Institute of Technology, AFIT/ENS, Building 640, 2950 P Street, Wright-Patterson Air Force Base, Ohio 45433-7765
Charles H. Reilly: Department of Industrial Engineering and Management Systems, University of Central Florida, 4000 Central Florida Boulevard, P.O. Box 162450, Orlando, Florida 32816-2450
Management Science, 2000, vol. 46, issue 2, 302-317
Abstract:
This paper presents the results of an empirical study of the effects of coefficient correlation structure and constraint slackness settings on the performance of solution procedures on synthetic two-dimensional knapsack problems (2KP). The population correlation structure among 2KP coefficients, the level of constraint slackness, and the type of correlation (product moment or rank) are varied in this study. Representative branch-and-bound and heuristic solution procedures are used to investigate the influence of these problem parameters on solution procedure performance. Population correlation structure, and in particular the interconstraint component of the correlation structure, is found to be a significant factor influencing the performance of both the algorithm and the heuristic. In addition, the interaction between constraint slackness and population correlation structure is found to influence solution procedure performance.
Keywords: product moment correlation induction; rank correlation induction; computational testing of algorithms/heuristics; empirical analysis of algorithms/heuristics; bidimensional knapsack problem; test problem generation (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)
Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.46.2.302.11930 (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:46:y:2000:i:2:p:302-317
Access Statistics for this article
More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().