A new algorithm for the Integer Knapsack Problem and its parallelization
Author
Abstract
Suggested Citation
DOI: 10.1007/BF02568586
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
- P. C. Gilmore & R. E. Gomory, 1965. "Multistage Cutting Stock Problems of Two and More Dimensions," Operations Research, INFORMS, vol. 13(1), pages 94-120, February.
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.- Jean-François Côté & Manuel Iori, 2018. "The Meet-in-the-Middle Principle for Cutting and Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 646-661, November.
- Amanda O. C. Ayres & Betania S. C. Campello & Washington A. Oliveira & Carla T. L. S. Ghidini, 2021. "A Bi-Integrated Model for coupling lot-sizing and cutting-stock problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 1047-1076, December.
- Parreño, F. & Alvarez-Valdes, R., 2021. "Mathematical models for a cutting problem in the glass manufacturing industry," Omega, Elsevier, vol. 103(C).
- Gregory S. Taylor & Yupo Chan & Ghulam Rasool, 2017. "A three-dimensional bin-packing model: exact multicriteria solution and computational complexity," Annals of Operations Research, Springer, vol. 251(1), pages 397-427, April.
- Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
- W. D. D. Madhavee & N. Saldin & U. C. Vaidyarathna & C. J. Jayawardene, 2018. "A Practical Application of the Generalized Cutting Stock Algorithm," Academic Journal of Applied Mathematical Sciences, Academic Research Publishing Group, vol. 4(3), pages 15-21, 03-2018.
- Mhand Hifi & Rym M'Hallah, 2005. "An Exact Algorithm for Constrained Two-Dimensional Two-Staged Cutting Problems," Operations Research, INFORMS, vol. 53(1), pages 140-150, February.
- Suliman, S.M.A., 2006. "A sequential heuristic procedure for the two-dimensional cutting-stock problem," International Journal of Production Economics, Elsevier, vol. 99(1-2), pages 177-185, February.
- M Hifi & M Michrafy, 2006. "A reactive local search-based algorithm for the disjunctively constrained knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(6), pages 718-726, June.
- Ramón Alvarez-Valdes & Rafael Martí & Jose M. Tamarit & Antonio Parajón, 2007. "GRASP and Path Relinking for the Two-Dimensional Two-Stage Cutting-Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 261-272, May.
- Chengbin Chu & Julien Antonio, 1999. "Approximation Algorithms to Solve Real-Life Multicriteria Cutting Stock Problems," Operations Research, INFORMS, vol. 47(4), pages 495-508, August.
- Bennell, J.A. & Cabo, M. & Martínez-Sykora, A., 2018. "A beam search approach to solve the convex irregular bin packing problem with guillotine guts," European Journal of Operational Research, Elsevier, vol. 270(1), pages 89-102.
- Hifi, Mhand & M'Hallah, Rym, 2006. "Strip generation algorithms for constrained two-dimensional two-staged cutting problems," European Journal of Operational Research, Elsevier, vol. 172(2), pages 515-527, July.
- Silva, Elsa & Oliveira, José Fernando & Silveira, Tiago & Mundim, Leandro & Carravilla, Maria Antónia, 2023. "The Floating-Cuts model: a general and flexible mixed-integer programming model for non-guillotine and guillotine rectangular cutting problems," Omega, Elsevier, vol. 114(C).
- Kaiyuan Liu & Hongyu Zhang & Chong Wang & Hui Li & Yongquan Chen & Qiong Chen, 2023. "Robust Optimization for the Two-Dimensional Strip-Packing Problem with Variable-Sized Bins," Mathematics, MDPI, vol. 11(23), pages 1-22, November.
- Teodor Gabriel Crainic & Guido Perboli & Roberto Tadei, 2008. "Extreme Point-Based Heuristics for Three-Dimensional Bin Packing," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 368-384, August.
- Gomory, Ralph, 2016. "Origin and early evolution of corner polyhedra," European Journal of Operational Research, Elsevier, vol. 253(3), pages 543-556.
- Alberto Caprara, 2008. "Packing d -Dimensional Bins in d Stages," Mathematics of Operations Research, INFORMS, vol. 33(1), pages 203-215, February.
- Kelly Cristina Poldi & Silvio Alexandre Araujo, 2016. "Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem," Annals of Operations Research, Springer, vol. 238(1), pages 497-520, March.
- Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
More about this item
Keywords
Dynamic Programming; Integer Programming; Knapsack Problem; Parallel Computing; Transputer Networks; PVM;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:spr:topjnl:v:3:y:1995:i:2:p:221-234. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.