The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance
Author
Abstract
Suggested Citation
DOI: 10.1287/mnsc.46.2.302.11930
Download full text from publisher
References listed on IDEAS
- Frieze, A. M. & Clarke, M. R. B., 1984. "Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses," European Journal of Operational Research, Elsevier, vol. 15(1), pages 100-109, January.
- Egon Balas & Clarence H. Martin, 1980. "Pivot and Complement--A Heuristic for 0-1 Programming," Management Science, INFORMS, vol. 26(1), pages 86-96, January.
- Stelios H. Zanakis, 1977. "Heuristic 0-1 Linear Programming: An Experimental Comparison of Three Methods," Management Science, INFORMS, vol. 24(1), pages 91-104, September.
- Yoshiaki Toyoda, 1975. "A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems," Management Science, INFORMS, vol. 21(12), pages 1417-1427, August.
- Monique Guignard & Moshe B. Rosenwein, 1989. "Technical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem," Operations Research, INFORMS, vol. 37(4), pages 658-663, August.
- Lokketangen, Arne & Glover, Fred, 1998. "Solving zero-one mixed integer programming problems using tabu search," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 624-658, April.
- J. N. Hooker, 1994. "Needed: An Empirical Science of Algorithms," Operations Research, INFORMS, vol. 42(2), pages 201-212, April.
- C. N. Potts & L. N. Van Wassenhove, 1988. "Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs," Management Science, INFORMS, vol. 34(7), pages 843-858, July.
- Freville, Arnaud & Plateau, Gerard, 1993. "An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 68(3), pages 413-421, August.
- Egon Balas & Eitan Zemel, 1980. "An Algorithm for Large Zero-One Knapsack Problems," Operations Research, INFORMS, vol. 28(5), pages 1130-1154, October.
- Marshall L. Fisher & R. Jaikumar & Luk N. Van Wassenhove, 1986. "A Multiplier Adjustment Method for the Generalized Assignment Problem," Management Science, INFORMS, vol. 32(9), pages 1095-1103, September.
- Mohammad M. Amini & Michael Racer, 1994. "A Rigorous Computational Comparison of Alternative Solution Methods for the Generalized Assignment Problem," Management Science, INFORMS, vol. 40(7), pages 868-890, July.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- Soumyadip Ghosh & Shane G. Henderson, 2002. "Chessboard Distributions and Random Vectors with Specified Marginals and Covariance Matrix," Operations Research, INFORMS, vol. 50(5), pages 820-834, October.
- Leo Lopes & Kate Smith-Miles, 2013. "Generating Applicable Synthetic Instances for Branch Problems," Operations Research, INFORMS, vol. 61(3), pages 563-577, June.
- 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.
- Charles H. Reilly, 2009. "Synthetic Optimization Problem Generation: Show Us the Correlations!," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 458-467, August.
- Jooken, Jorik & Leyman, Pieter & De Causmaecker, Patrick, 2023. "Features for the 0-1 knapsack problem based on inclusionwise maximal solutions," European Journal of Operational Research, Elsevier, vol. 311(1), pages 36-55.
- Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
- Jorge A. Sefair & Oscar Guaje & Andrés L. Medaglia, 2021. "A column-oriented optimization approach for the generation of correlated random vectors," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 777-808, September.
- Reilly, Charles H. & Sapkota, Nabin, 2015. "A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances," European Journal of Operational Research, Elsevier, vol. 241(3), pages 642-652.
- Iain Dunning & Swati Gupta & John Silberholz, 2018. "What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 608-624, August.
- Arnaud Fréville & SaÏd Hanafi, 2005. "The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects," Annals of Operations Research, Springer, vol. 139(1), pages 195-227, October.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Charles H. Reilly, 2009. "Synthetic Optimization Problem Generation: Show Us the Correlations!," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 458-467, 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.
- Hill, Raymond R. & Reilly, Charles H., 2000. "Multivariate composite distributions for coefficients in synthetic optimization problems," European Journal of Operational Research, Elsevier, vol. 121(1), pages 64-77, February.
- Arnaud Fréville & SaÏd Hanafi, 2005. "The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects," Annals of Operations Research, Springer, vol. 139(1), pages 195-227, October.
- Reilly, Charles H. & Sapkota, Nabin, 2015. "A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances," European Journal of Operational Research, Elsevier, vol. 241(3), pages 642-652.
- Amini, Mohammad M. & Racer, Michael & Ghandforoush, Parviz, 1998. "Heuristic sensitivity analysis in a combinatoric environment: An exposition and case study," European Journal of Operational Research, Elsevier, vol. 108(3), pages 604-617, August.
- Haddadi, Salim & Ouzia, Hacene, 2004. "Effective algorithm and heuristic for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 153(1), pages 184-190, February.
- Cattrysse, D. G. & van Wassenhove, L. N., 1990. "A Survey Of Algorithms For The Generalized Assignment Problem," Econometric Institute Archives 272389, Erasmus University Rotterdam.
- June S. Park & Byung Ha Lim & Youngho Lee, 1998. "A Lagrangian Dual-Based Branch-and-Bound Algorithm for the Generalized Multi-Assignment Problem," Management Science, INFORMS, vol. 44(12-Part-2), pages 271-282, December.
- H. Edwin Romeijn & Dolores Romero Morales, 2001. "Generating Experimental Data for the Generalized Assignment Problem," Operations Research, INFORMS, vol. 49(6), pages 866-878, December.
- Narciso, Marcelo G. & Lorena, Luiz Antonio N., 1999. "Lagrangean/surrogate relaxation for generalized assignment problems," European Journal of Operational Research, Elsevier, vol. 114(1), pages 165-177, April.
- Diaz, Juan A. & Fernandez, Elena, 2001. "A Tabu search heuristic for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 132(1), pages 22-38, July.
- Dimitris Bertsimas & Ramazan Demir, 2002. "An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems," Management Science, INFORMS, vol. 48(4), pages 550-565, April.
- Martello, Silvano & Toth, Paolo, 1995. "The bottleneck generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 83(3), pages 621-638, June.
- Marianna De Santis & Stefano Lucidi & Francesco Rinaldi, 2011. "A new class of functions for measuring solution integrality in the Feasibility Pump approach," DIS Technical Reports 2011-08, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
- Corbett, Charles J. & Debets, Frank J.C. & Van Wassenhove, Luk N., 1995. "Decentralization of responsibility for site decontamination projects: A budget allocation approach," European Journal of Operational Research, Elsevier, vol. 86(1), pages 103-119, October.
- Altay, Nezih & Robinson Jr., Powell E. & Bretthauer, Kurt M., 2008. "Exact and heuristic solution approaches for the mixed integer setup knapsack problem," European Journal of Operational Research, Elsevier, vol. 190(3), pages 598-609, November.
- Pessoa, Artur Alves & Hahn, Peter M. & Guignard, Monique & Zhu, Yi-Rong, 2010. "Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique," European Journal of Operational Research, Elsevier, vol. 206(1), pages 54-63, October.
- Marianna De Santis & Stefano Lucidi & Francesco Rinaldi, 2013. "A new class of functions for measuring solution integrality in the Feasibility Pump approach: Complete Results," DIAG Technical Reports 2013-05, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
- Helena Ramalhinho-Lourenço & Daniel Serra, 1998. "Adaptive approach heuristics for the generalized assignment problem," Economics Working Papers 288, Department of Economics and Business, Universitat Pompeu Fabra.
More about this item
Keywords
product moment correlation induction; rank correlation induction; computational testing of algorithms/heuristics; empirical analysis of algorithms/heuristics; bidimensional knapsack problem; test problem generation;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:46:y:2000:i:2:p:302-317. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.