Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem
Author
Abstract
Suggested Citation
DOI: 10.1287/ijoc.2020.1014
Download full text from publisher
References listed on IDEAS
- Nicos Christofides & Charles Whitlock, 1977. "An Algorithm for Two-Dimensional Cutting Problems," Operations Research, INFORMS, vol. 25(1), pages 30-44, February.
- Wascher, Gerhard & Hau[ss]ner, Heike & Schumann, Holger, 2007. "An improved typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December.
- 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.
- 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.
- Michele Monaci & Paolo Toth, 2006. "A Set-Covering-Based Heuristic Approach for Bin-Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 71-85, February.
- Dell’Amico, Mauro & Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2019. "Mathematical models and decomposition methods for the multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(3), pages 886-899.
- Sándor P. Fekete & Jörg Schepers & Jan C. van der Veen, 2007. "An Exact Algorithm for Higher-Dimensional Orthogonal Packing," Operations Research, INFORMS, vol. 55(3), pages 569-587, June.
- Vitor Nesello & Maxence Delorme & Manuel Iori & Anand Subramanian, 2018. "Mathematical models and decomposition algorithms for makespan minimization in plastic rolls production," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 69(3), pages 326-339, March.
- WOLSEY, Laurence A., 1975. "Faces for a linear inequality in 0-1 variables," LIDAM Reprints CORE 218, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
- Baldacci, Roberto & Boschetti, Marco A., 2007. "A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1136-1149, December.
- Manuel Iori & Silvano Martello, 2010. "Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 4-27, July.
- Andrea Lodi & Silvano Martello & Daniele Vigo, 2004. "TSpack: A Unified Tabu Search Code for Multi-Dimensional Bin Packing Problems," Annals of Operations Research, Springer, vol. 131(1), pages 203-213, October.
- François Clautiaux & Cláudio Alves & José Valério de Carvalho, 2010. "A survey of dual-feasible and superadditive functions," Annals of Operations Research, Springer, vol. 179(1), pages 317-342, September.
- Clautiaux, Francois & Carlier, Jacques & Moukrim, Aziz, 2007. "A new exact method for the two-dimensional orthogonal packing problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1196-1211, December.
- Manuel Iori & Silvano Martello, 2010. "Rejoinder on: Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 41-42, July.
- Leung, Stephen C.H. & Zhang, Defu & Sim, Kwang Mong, 2011. "A two-stage intelligent search algorithm for the two-dimensional strip packing problem," European Journal of Operational Research, Elsevier, vol. 215(1), pages 57-69, November.
- Marco Antonio Boschetti & Lorenza Montaletti, 2010. "An Exact Algorithm for the Two-Dimensional Strip-Packing Problem," Operations Research, INFORMS, vol. 58(6), pages 1774-1791, December.
- J. N. Hooker, 2007. "Planning and Scheduling by Logic-Based Benders Decomposition," Operations Research, INFORMS, vol. 55(3), pages 588-602, June.
- F. Parreño & R. Alvarez-Valdes & J. Oliveira & J. Tamarit, 2010. "A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing," Annals of Operations Research, Springer, vol. 179(1), pages 203-220, September.
- 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.
- Castro, Pedro M. & Oliveira, José F., 2011. "Scheduling inspired models for two-dimensional packing problems," European Journal of Operational Research, Elsevier, vol. 215(1), pages 45-56, November.
- Guntram Scheithauer, 2018. "Introduction to Cutting and Packing Optimization," International Series in Operations Research and Management Science, Springer, number 978-3-319-64403-5, January.
- Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2016. "Bin packing and cutting stock problems: Mathematical models and exact algorithms," European Journal of Operational Research, Elsevier, vol. 255(1), pages 1-20.
- Oluf Faroe & David Pisinger & Martin Zachariasen, 2003. "Guided Local Search for the Three-Dimensional Bin-Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 267-283, August.
- Silvano Martello & Daniele Vigo, 1998. "Exact Solution of the Two-Dimensional Finite Bin Packing Problem," Management Science, INFORMS, vol. 44(3), pages 388-399, March.
- David Pisinger & Mikkel Sigurd, 2007. "Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 36-51, February.
- Maxence Delorme & Manuel Iori, 2020. "Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 101-119, January.
- Silvano Martello & Michele Monaci & Daniele Vigo, 2003. "An Exact Approach to the Strip-Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 310-319, August.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- Hu, Peng & Chu, Feng & Dolgui, Alexandre & Chu, Chengbin & Liu, Ming, 2024. "Integrated multi-product reverse supply chain design and disassembly line balancing under uncertainty," Omega, Elsevier, vol. 126(C).
- Mao, Zhaofang & Fu, Enyuan & Huang, Dian & Fang, Kan & Chen, Lin, 2024. "Combinatorial Benders decomposition for single machine scheduling in additive manufacturing with two-dimensional packing constraints," European Journal of Operational Research, Elsevier, vol. 317(3), pages 890-905.
- Mathijs Barkel & Maxence Delorme, 2023. "Arcflow Formulations and Constraint Generation Frameworks for the Two Bar Charts Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 475-494, March.
- Haouari, Mohamed & Mhiri, Mariem, 2024. "Lower and upper bounding procedures for the bin packing problem with concave loading cost," European Journal of Operational Research, Elsevier, vol. 312(1), pages 56-69.
- Amin Abbasi-Pooya & Michael T. Lash, 2024. "The third party logistics provider freight management problem: a framework and deep reinforcement learning approach," Annals of Operations Research, Springer, vol. 339(1), pages 965-1024, 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.- 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.
- Jean-François Côté & Mauro Dell'Amico & Manuel Iori, 2014. "Combinatorial Benders' Cuts for the Strip Packing Problem," Operations Research, INFORMS, vol. 62(3), pages 643-661, June.
- Nestor M Cid-Garcia & Yasmin A Rios-Solis, 2020. "Positions and covering: A two-stage methodology to obtain optimal solutions for the 2d-bin packing problem," PLOS ONE, Public Library of Science, vol. 15(4), pages 1-22, April.
- Krzysztof Fleszar, 2016. "An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 703-720, November.
- Jean-François Côté & Michel Gendreau & Jean-Yves Potvin, 2020. "The Vehicle Routing Problem with Stochastic Two-Dimensional Items," Transportation Science, INFORMS, vol. 54(2), pages 453-469, March.
- Silva, Allyson & Coelho, Leandro C. & Darvish, Maryam & Renaud, Jacques, 2022. "A cutting plane method and a parallel algorithm for packing rectangles in a circular container," European Journal of Operational Research, Elsevier, vol. 303(1), pages 114-128.
- Bortfeldt, Andreas & Wäscher, Gerhard, 2013. "Constraints in container loading – A state-of-the-art review," European Journal of Operational Research, Elsevier, vol. 229(1), pages 1-20.
- 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).
- Jean-François Côté & Michel Gendreau & Jean-Yves Potvin, 2014. "An Exact Algorithm for the Two-Dimensional Orthogonal Packing Problem with Unloading Constraints," Operations Research, INFORMS, vol. 62(5), pages 1126-1141, October.
- F. Parreño & R. Alvarez-Valdes & J. Oliveira & J. Tamarit, 2010. "A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing," Annals of Operations Research, Springer, vol. 179(1), pages 203-220, September.
- Gonçalves, José Fernando & Resende, Mauricio G.C., 2013. "A biased random key genetic algorithm for 2D and 3D bin packing problems," International Journal of Production Economics, Elsevier, vol. 145(2), pages 500-510.
- Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
- Marco Antonio Boschetti & Lorenza Montaletti, 2010. "An Exact Algorithm for the Two-Dimensional Strip-Packing Problem," Operations Research, INFORMS, vol. 58(6), pages 1774-1791, December.
- Stéphane Grandcolas & Cyril Pain-Barre, 2022. "A hybrid metaheuristic for the two-dimensional strip packing problem," Annals of Operations Research, Springer, vol. 309(1), pages 79-102, February.
- Côté, J.F. & Guastaroba, G. & Speranza, M.G., 2017. "The value of integrating loading and routing," European Journal of Operational Research, Elsevier, vol. 257(1), pages 89-105.
- Jéssica Gabriela Almeida Cunha & Vinícius Loti de Lima & Thiago Alves Queiroz, 2020. "Grids for cutting and packing problems: a study in the 2D knapsack problem," 4OR, Springer, vol. 18(3), pages 293-339, September.
- Mathijs Barkel & Maxence Delorme, 2023. "Arcflow Formulations and Constraint Generation Frameworks for the Two Bar Charts Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 475-494, March.
- Wei, Lijun & Oon, Wee-Chong & Zhu, Wenbin & Lim, Andrew, 2011. "A skyline heuristic for the 2D rectangular packing and strip packing problems," European Journal of Operational Research, Elsevier, vol. 215(2), pages 337-346, December.
- Wei, Lijun & Oon, Wee-Chong & Zhu, Wenbin & Lim, Andrew, 2013. "A goal-driven approach to the 2D bin packing and variable-sized bin packing problems," European Journal of Operational Research, Elsevier, vol. 224(1), pages 110-121.
- de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
More about this item
Keywords
two-dimensional bin packing problem; exact algorithm; Benders decomposition; combinatorial Benders cut;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:orijoc:v:33:y:2021:i:3:p:963-978. 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.