The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance
AbstractThis 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by INFORMS in its journal Management Science.
Volume (Year): 46 (2000)
Issue (Month): 2 (February)
product moment correlation induction; rank correlation induction; computational testing of algorithms/heuristics; empirical analysis of algorithms/heuristics; bidimensional knapsack problem; test problem generation;
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Vasquez, Michel & Vimont, Yannick, 2005. "Improved results on the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 165(1), pages 70-81, August.
- Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc).
If references are entirely missing, you can add them using this form.