An optimization framework for solving large scale multidemand multidimensional knapsack problem instances employing a novel core identification heuristic
Author
Abstract
Suggested Citation
DOI: 10.1016/j.ejor.2024.08.025
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- Lai, Xiangjing & Hao, Jin-Kao & Yue, Dong, 2019. "Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 35-48.
- Silvano Martello & Paolo Toth, 1988. "A New Algorithm for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 34(5), pages 633-644, May.
- Soyster, A. L. & Lev, B. & Slivka, W., 1978. "Zero-one programming with many variables and few constraints," European Journal of Operational Research, Elsevier, vol. 2(3), pages 195-201, May.
- George J. Beaujon & Samuel P. Marin & Gary C. McDonald, 2001. "Balancing and optimizing a portfolio of R&D projects," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(1), pages 18-40, February.
- Al-Shihabi, Sameh, 2021. "A Novel Core-Based Optimization Framework for Binary Integer Programs- the Multidemand Multidimesional Knapsack Problem as a Test Problem," Operations Research Perspectives, Elsevier, vol. 8(C).
- Paola Cappanera & Marco Trubian, 2005. "A Local-Search-Based Heuristic for the Demand-Constrained Multidimensional Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 82-98, February.
- Michael J. Magazine & Maw-Sheng Chern, 1984. "A Note on Approximation Schemes for Multidimensional Knapsack Problems," Mathematics of Operations Research, INFORMS, vol. 9(2), pages 244-247, May.
- J. E. Beasley, 1990. "A lagrangian heuristic for set‐covering problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(1), pages 151-164, February.
- Egon Balas & Eitan Zemel, 1980. "An Algorithm for Large Zero-One Knapsack Problems," Operations Research, INFORMS, vol. 28(5), pages 1130-1154, October.
- Wishon, Christopher & Villalobos, J. Rene, 2016. "Robust efficiency measures for linear knapsack problem variants," European Journal of Operational Research, Elsevier, vol. 254(2), pages 398-409.
- Saïd Hanafi & Christophe Wilbaut, 2011. "Improved convergent heuristics for the 0-1 multidimensional knapsack problem," Annals of Operations Research, Springer, vol. 183(1), pages 125-142, March.
- Renata Mansini & M. Grazia Speranza, 2012. "CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 399-415, August.
- Christophe Wilbaut & Saïd Hanafi & Igor Machado Coelho & Abilio Lucena, 2022. "The Knapsack Problem and Its Variants: Formulations and Solution Methods," Springer Books, in: Saïd Salhi & John Boylan (ed.), The Palgrave Handbook of Operations Research, chapter 0, pages 105-151, Springer.
- David Pisinger, 1999. "Core Problems in Knapsack Algorithms," Operations Research, INFORMS, vol. 47(4), pages 570-575, August.
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.- Al-Shihabi, Sameh, 2021. "A Novel Core-Based Optimization Framework for Binary Integer Programs- the Multidemand Multidimesional Knapsack Problem as a Test Problem," Operations Research Perspectives, Elsevier, vol. 8(C).
- Wishon, Christopher & Villalobos, J. Rene, 2016. "Robust efficiency measures for linear knapsack problem variants," European Journal of Operational Research, Elsevier, vol. 254(2), pages 398-409.
- Lai, Xiangjing & Hao, Jin-Kao & Yue, Dong, 2019. "Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 35-48.
- 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.
- Renata Mansini & M. Grazia Speranza, 2012. "CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 399-415, August.
- Jakob Puchinger & Günther R. Raidl & Ulrich Pferschy, 2010. "The Multidimensional Knapsack Problem: Structure and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 250-265, May.
- Freville, Arnaud, 2004. "The multidimensional 0-1 knapsack problem: An overview," European Journal of Operational Research, Elsevier, vol. 155(1), pages 1-21, May.
- José García & Paola Moraga & Broderick Crawford & Ricardo Soto & Hernan Pinto, 2022. "Binarization Technique Comparisons of Swarm Intelligence Algorithm: An Application to the Multi-Demand Multidimensional Knapsack Problem," Mathematics, MDPI, vol. 10(17), pages 1-20, September.
- Nicholas G. Hall & Marc E. Posner, 2007. "Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures," Operations Research, INFORMS, vol. 55(4), pages 703-716, August.
- Silvano Martello & Paolo Toth, 2003. "An Exact Algorithm for the Two-Constraint 0--1 Knapsack Problem," Operations Research, INFORMS, vol. 51(5), pages 826-835, October.
- Raka Jovanovic & Stefan Voß, 2024. "Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 46(4), pages 1329-1365, December.
- M Hifi & M Michrafy & A Sbihi, 2004. "Heuristic algorithms for the multiple-choice multidimensional knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1323-1332, December.
- Silvano Martello & David Pisinger & Paolo Toth, 1999. "Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 45(3), pages 414-424, March.
- Pisinger, David, 1995. "Avoiding anomalies in the 2 algorithm by Martello and Toth," European Journal of Operational Research, Elsevier, vol. 82(1), pages 206-208, April.
- Mavrotas, George & Figueira, José Rui & Florios, Kostas, 2009. "Solving the bi-objective multidimensional knapsack problem exploiting the concept of core," MPRA Paper 105087, University Library of Munich, Germany.
- Mavrotas, George & Florios, Kostas & Figueira, José Rui, 2015. "An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: A computational study and comparison with meta-heuristics," Applied Mathematics and Computation, Elsevier, vol. 270(C), pages 25-43.
- Gendron, Bernard & Hanafi, Saïd & Todosijević, Raca, 2018. "Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design," European Journal of Operational Research, Elsevier, vol. 268(1), pages 70-81.
- 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.
- Charles H. Reilly, 2009. "Synthetic Optimization Problem Generation: Show Us the Correlations!," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 458-467, August.
- David Pisinger, 1999. "Core Problems in Knapsack Algorithms," Operations Research, INFORMS, vol. 47(4), pages 570-575, August.
More about this item
Keywords
Core problem; Multidemand multidimensional knapsack problem; Exact solution; Tabu search; Local-branching;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:eee:ejores:v:320:y:2025:i:3:p:496-504. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.