{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T18:32:41Z","timestamp":1772821961813,"version":"3.50.1"},"reference-count":44,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T00:00:00Z","timestamp":1739923200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Ministry of Culture and Innovation from the National Fund for Research, Development and Innovation","award":["2024-2.1.1-EK\u00d6P"],"award-info":[{"award-number":["2024-2.1.1-EK\u00d6P"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this work, the Bin Packing combinatorial optimization problem is studied from the practical side. The focus is on the Falkenauer T benchmark class, which is a collection of 80 problem instances that are considered hard to handle algorithmically. Contrary to this widely accepted view, we show that the instances of this benchmark class can be solved relatively easily, without applying any sophisticated methods like metaheuristics. A new algorithm is proposed, which can operate in two modes: either using backtrack or local search to find optimal packing. In theory, both operating modes are guaranteed to find a solution. Computational results show that all instances of the Falkenauer T benchmark class can be solved in a total of 1.18 s and 2.39 s with the two operating modes alone, or 0.2 s when running in parallel.<\/jats:p>","DOI":"10.3390\/a18020115","type":"journal-article","created":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T03:29:53Z","timestamp":1739935793000},"page":"115","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Solution of Bin Packing Instances in Falkenauer T Class: Not So Hard"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4909-6694","authenticated-orcid":false,"given":"Gy\u00f6rgy","family":"D\u00f3sa","sequence":"first","affiliation":[{"name":"Mathematical Department, Faculty of Information Technology, University of Pannonia, 8200 Veszpr\u00e9m, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5000-3395","authenticated-orcid":false,"given":"Andr\u00e1s","family":"\u00c9les","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Systems Technology, Faculty of Information Technology, University of Pannonia, 8200 Veszpr\u00e9m, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2457-2003","authenticated-orcid":false,"given":"Angshuman Robin","family":"Goswami","sequence":"additional","affiliation":[{"name":"Mathematical Department, Faculty of Information Technology, University of Pannonia, 8200 Veszpr\u00e9m, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Istv\u00e1n","family":"Szalkai","sequence":"additional","affiliation":[{"name":"Mathematical Department, Faculty of Information Technology, University of Pannonia, 8200 Veszpr\u00e9m, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3235-9221","authenticated-orcid":false,"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Systems Technology, Faculty of Information Technology, University of Pannonia, 8200 Veszpr\u00e9m, Hungary"},{"name":"HUN-REN Alfr\u00e9d R\u00e9nyi Institute of Mathematics, 1053 Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,2,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Hochbaum, D. (1997). Approximation algorithms for bin packing: A survey. Approximation Algorithms for NP-Hard Problems, PWS Publishing.","DOI":"10.1145\/261342.571216"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Pardalos, P.M., Du, D.-Z., and Graham, R.L. (2013). Bin packing approximation algorithms: Survey and classification. Handbook of Combinatorial Optimization, Springer.","DOI":"10.1007\/978-1-4419-7997-1"},{"key":"ref_3","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computer and Intractability: A Guide to the Theory of NP-Completeness, Freeman."},{"key":"ref_4","unstructured":"Johnson, D.S. (1973). Near-Optimal Bin Packing Algorithms. [Ph.D. Thesis, MIT]."},{"key":"ref_5","unstructured":"Ullman, J.D. (1971). The Performance of a Memory Allocation Algorithm, Princeton University. Technical Report 100."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Romero, S.V., Osaba, E., Villar-Rodriguez, E., and Asla, A. (2023). Solving Logistic-Oriented Bin Packing Problems Through a Hybrid Quantum-Classical Approach. arXiv.","DOI":"10.1109\/ITSC57777.2023.10422581"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Murdivien, S.A., and Um, J. (2023). BoxStacker: Deep Reinforcement Learning for 3D Bin Packing Problem in Virtual Environment of Logistics Systems. Sensors, 23.","DOI":"10.3390\/s23156928"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1016\/j.ejor.2016.02.040","article-title":"Logistics capacity planning: A stochastic bin packing formulation and a progressive hedging meta-heuristic","volume":"253","author":"Crainic","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Moura, A., Pinto, T., Alves, C., and Val\u00e9rio de Carvalho, J. (2023). A Matheuristic Approach to the Integration of Three-Dimensional Bin Packing Problem and Vehicle Routing Problem with Simultaneous Delivery and Pickup. Mathematics, 11.","DOI":"10.3390\/math11030713"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Pantoja-Benavides, G., Giraldo, D., Montes, A., Garc\u00eda, A., Rodr\u00edguez, C., Mar\u00edn, C., and \u00c1lvarez-Mart\u00ednez, D. (2024). Comprehensive Review of Robotized Freight Packing. Logistics, 8.","DOI":"10.3390\/logistics8030069"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Yang, Y., Xiao, M., and Li, W. (2024). Semi-Online Algorithms for the Hierarchical Extensible Bin-Packing Problem and Early Work Problem. Computation, 12.","DOI":"10.3390\/computation12040068"},{"key":"ref_12","unstructured":"Dosa, G., and Sgall, J. (March, January 27). First Fit bin packing: A tight analysis. Proceedings of the 30th Anniversary Symposium on Theoretical Aspects of Computer Science (STACS2013), LIPIcs 3, Kiel, Germany."},{"key":"ref_13","first-page":"429","article-title":"Optimal Analysis of Best Fit Bin Packing","volume":"Volume 8572","author":"Esparza","year":"2014","journal-title":"Proceedings of the ICALP 2014"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Dosa, G. (2007, January 7\u20139). The tight bound of First Fit Decreasing bin-packing algorithm is FFD(I) \u2264 11\/9 \u2264 OPT(I) + 6\/9. Proceedings of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE), Hangzhou, China. Lecture Notes in Computer Sciences.","DOI":"10.1007\/978-3-540-74450-4_1"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tcs.2013.09.007","article-title":"Tight absolute bound for First Fit Decreasing bin-packing: FFD(L) \u2264 11\/9\u00b7OPT(L) + 6\/9","volume":"510","author":"Dosa","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2016.04.030","article-title":"Bin Packing and Cutting Stock Problems: Mathematical Models and Exact Algorithms","volume":"255","author":"Delorme","year":"2016","journal-title":"Eur. J. Operational Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.ejor.2004.08.036","article-title":"A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting","volume":"171","author":"Belov","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1996","DOI":"10.1007\/BF00226291","article-title":"A hybrid grouping genetic algorithm for bin packing","volume":"2","author":"Falkenauer","year":"1996","journal-title":"J. Heuristics"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1023\/B:HEUR.0000026267.44673.ed","article-title":"A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem","volume":"10","author":"Alvim","year":"2004","journal-title":"J. Heuristics"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s10100-020-00695-5","article-title":"A hybrid evolutionary algorithm for the offline Bin Packing Problem","volume":"29","author":"Borgulya","year":"2021","journal-title":"Cent. Eur. J. Oper."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/j.ejor.2010.11.004","article-title":"Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem","volume":"210","author":"Fleszar","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.cor.2016.06.009","article-title":"Consistent neighborhood search for one-dimensional bin packing and two-dimensional vector packing","volume":"76","author":"Vasquez","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Xu, H., Shen, Y., Sun, Y., and Li, X. (2024, January 14\u201318). Machine Learning-Enhanced Ant Colony Optimization for Column Generation. Proceedings of the GECCO \u201924: Proceedings of the Genetic and Evolutionary Computation Conference, Melbourne, VIC, Australia.","DOI":"10.1145\/3638529.3654043"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.ejor.2024.08.007","article-title":"Bounds and heuristic algorithms for the bin packing problem with minimum color fragmentation","volume":"320","author":"Barkel","year":"2025","journal-title":"Eur. J. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"126196","DOI":"10.1016\/j.eswa.2024.126196","article-title":"Transportation mode detection through spatial attention-based transductive long short-term memory and off-policy feature selection","volume":"267","author":"Merikhipour","year":"2025","journal-title":"Expert Syst. Appl."},{"key":"ref_26","first-page":"149","article-title":"Hybrid heuristic for the one-dimensional cutting stock problem with usable leftovers and additional operating constraints","volume":"15","author":"Bertolini","year":"2024","journal-title":"Int. J. Ind. Eng. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"\u00c1brah\u00e1m, G., D\u00f3sa, G., Dulai, T., Tuza, Z., and Werner-Stark, \u00c1. (2021). Efficient Pre-Solve Algorithms for the Schwerin and Falkenauer_U Bin Packing Benchmark Problems for Getting Optimal Solutions with High Probability. Mathematics, 9.","DOI":"10.3390\/math9131540"},{"key":"ref_28","unstructured":"(2025, February 18). Bin Packing Benchmarks of Homepage Unibo. Available online: https:\/\/site.unibo.it\/operations-research\/en\/research\/bpplib-a-bin-packing-problem-library."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1016\/S0305-0548(96)00082-2","article-title":"Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem","volume":"24","author":"Scholl","year":"1997","journal-title":"Comput. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF01539705","article-title":"Heuristics for the integer one-dimensional cutting stock problem: A computational study","volume":"18","author":"Gau","year":"1996","journal-title":"OR Spectr."},{"key":"ref_31","first-page":"377","article-title":"The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP","volume":"4","author":"Schwerin","year":"1997","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_32","unstructured":"Schoenfield, J.E. (2002). Fast, Exact Solution of Open Bin Packing Problems Without Linear Programming, US Army Space and Missile Defense Command. Technical Report."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0166-218X(90)90094-S","article-title":"Lower bounds and reduction procedures for the bin packing problem","volume":"28","author":"Martello","year":"1990","journal-title":"Discret. Appl. Math."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/s101070100243","article-title":"New classes of fast lower bounds for bin packing problems","volume":"91","author":"Fekete","year":"2001","journal-title":"Math. Program."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s00373-008-0789-5","article-title":"Monochromatic and heterochromatic subgraphs in edge-colored graphs\u2014A survey","volume":"24","author":"Kano","year":"2008","journal-title":"Graphs Comb."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Fujita, S., Magnant, C., Mao, Y., and Ozeki, K. (2014). Rainbow generalizations of Ramsey theory\u2014A dynamic survey. Theory Appl. Graphs, 1.","DOI":"10.20429\/tag.2014.000101"},{"key":"ref_37","first-page":"187","article-title":"Long rainbow paths and rainbow cycles in edge colored graphs\u2014A survey","volume":"317","author":"Chen","year":"2018","journal-title":"Appl. Math. Comput."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Caro, Y., and Tuza, Z. (2025). Monochromatic graph decompositions and monochromatic piercing inspired by anti-Ramsey colorings. arXiv.","DOI":"10.1016\/j.dam.2024.12.009"},{"key":"ref_39","first-page":"9","article-title":"Rainbow perfect and near-perfect matchings in complete graphs with edges colored by circular distance","volume":"9","author":"Saito","year":"2022","journal-title":"Theory Appl. Graphs"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.tcs.2013.12.013","article-title":"Complexity results for rainbow matchings","volume":"524","author":"Le","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-031-78369-2_3","article-title":"Rainbow greedy matching algorithms","volume":"Volume 220","author":"Nikeghbali","year":"2025","journal-title":"Optimization, Discrete Mathematics and Applications to Data Sciences"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1017\/S0963548320000620","article-title":"Full rainbow matchings in graphs and hypergraphs","volume":"30","author":"Gao","year":"2021","journal-title":"Comb. Probab. Comput."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"12441","DOI":"10.1093\/imrn\/rnac180","article-title":"Short proofs of rainbow matchings results","volume":"14","author":"Correia","year":"2023","journal-title":"Int. Math. Res. Not."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.endm.2017.06.039","article-title":"Rainbow spanning subgraphs in bounded edge\u2013colourings of graphs with large minimum degree","volume":"61","author":"Cano","year":"2017","journal-title":"Electron. Notes Discret. Math."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/2\/115\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:37:26Z","timestamp":1760027846000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/2\/115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,19]]},"references-count":44,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,2]]}},"alternative-id":["a18020115"],"URL":"https:\/\/doi.org\/10.3390\/a18020115","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,19]]}}}