{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T17:42:47Z","timestamp":1770831767893,"version":"3.50.1"},"reference-count":38,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2018,6,22]],"date-time":"2018-06-22T00:00:00Z","timestamp":1529625600000},"content-version":"vor","delay-in-days":82,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2017,3,16]]},"published-print":{"date-parts":[[2018,4]]},"abstract":"<jats:p>We address the two-dimensional bin packing problem with fixed orientation. This problem requires packing a set of small rectangular items into a minimum number of standard two-dimensional bins. It is a notoriously intractable combinatorial optimization problem and has numerous applications in packing and cutting. The contribution of this paper is twofold. First, we propose a comprehensive theoretical analysis of lower bounds and we elucidate dominance relationships. We show that a previously presented dominance result is incorrect. Second, we present the results of an extensive computational study that was carried out, on a large set of 500 benchmark instances, to assess the empirical performance of the lower bounds. We found that the so-called Carlier-Clautiaux-Moukrim lower bounds exhibits an excellent relative performance and yields the tightest value for all of the benchmark instances.<\/jats:p>","DOI":"10.1051\/ro\/2017019","type":"journal-article","created":{"date-parts":[[2017,3,20]],"date-time":"2017-03-20T07:35:00Z","timestamp":1489995300000},"page":"391-414","source":"Crossref","is-referenced-by-count":10,"title":["A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem"],"prefix":"10.1051","volume":"52","author":[{"given":"Mehdi","family":"Serairi","sequence":"first","affiliation":[]},{"given":"Mohamed","family":"Haouari","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2018,6,22]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.ejor.2013.08.011","volume":"233","author":"Alves","year":"2015","journal-title":"Eur. J. Oper. Res"},{"key":"R2","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1057\/jors.1987.70","volume":"38","author":"Berkey","year":"1987","journal-title":"J. Oper. Res. Soc"},{"key":"R3","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1111\/j.1475-3995.2009.00701.x","volume":"16","author":"Bortfeldt","year":"2009","journal-title":"Inter. Trans. Oper. Res"},{"key":"R4","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.dam.2003.08.004","volume":"140","author":"Boschetti","year":"2004","journal-title":"Discrete Appl. Math"},{"key":"R5","doi-asserted-by":"crossref","first-page":"1774","DOI":"10.1287\/opre.1100.0833","volume":"58","author":"Boschetti","year":"2010","journal-title":"Oper. Res"},{"key":"R6","first-page":"27","volume":"4OR","author":"Boschetti","year":"2003","journal-title":"The two-dimensional finite bin packing problem, Part I: New lower bounds for the oriented case"},{"key":"R7","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/j.disopt.2010.03.003","volume":"7","author":"Caprara","year":"2010","journal-title":"Discrete Optimiz"},{"key":"R8","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s10107-007-0184-7","volume":"118","author":"Caprara","year":"2009","journal-title":"Math. Progr"},{"key":"R9","doi-asserted-by":"crossref","first-page":"2223","DOI":"10.1016\/j.cor.2005.08.012","volume":"34","author":"Carlier","year":"2007","journal-title":"Comput. Oper. Res"},{"key":"R10","doi-asserted-by":"crossref","first-page":"1452","DOI":"10.1016\/j.ejor.2005.09.034","volume":"176","author":"Carlier","year":"2007","journal-title":"Europ. J. Oper. Res"},{"key":"R11","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.ejor.2007.08.007","volume":"191","author":"Cintra","year":"2008","journal-title":"Europ. J. Oper. Res"},{"key":"R12","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/j.orl.2006.06.007","volume":"35","author":"Clautiaux","year":"2007","journal-title":"Oper. Res. Lett"},{"key":"R13","doi-asserted-by":"crossref","first-page":"1196","DOI":"10.1016\/j.ejor.2005.12.048","volume":"183","author":"Clautiaux","year":"2007","journal-title":"Europ. J. Oper. Res"},{"key":"R14","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s10479-008-0453-8","volume":"179","author":"Clautiaux","year":"2010","journal-title":"Ann. Oper. Res"},{"key":"R15","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1287\/opre.2013.1248","volume":"62","author":"C\u00f4t\u00e9","year":"2014","journal-title":"Oper. Res"},{"key":"R16","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.ejor.2014.06.032","volume":"240","author":"Cui","year":"2015","journal-title":"Europ. J. Oper. Res"},{"key":"R17","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1287\/ijoc.7.2.191","volume":"7","author":"Dell\u2019Amico","year":"1995","journal-title":"ORSA J. Comput"},{"key":"R18","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1016\/j.cor.2007.12.004","volume":"36","author":"Egeblad","year":"2009","journal-title":"Comput. Oper. Res"},{"key":"R19","first-page":"311","volume":"60","author":"Fekete","year":"2001","journal-title":"Math. Program"},{"key":"R20","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/s001860400376","volume":"60","author":"Fekete","year":"2004","journal-title":"Math. Methods Oper. Res"},{"key":"R21","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1287\/opre.1060.0369","volume":"55","author":"Fekete","year":"2007","journal-title":"Oper. Res"},{"key":"R22","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1016\/j.cor.2007.10.021","volume":"36","author":"Fuellerer","year":"2009","journal-title":"Comput. Oper. Res"},{"key":"R23","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1002\/net.20192","volume":"51","author":"Gendreau","year":"2008","journal-title":"Networks"},{"key":"R24","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0377-2217(93)E0278-6","volume":"83","author":"Hadjiconstantinou","year":"1995","journal-title":"Europ. J. Oper. Res"},{"key":"R25","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.ejor.2014.03.049","volume":"238","author":"Hong","year":"2014","journal-title":"Europ. J. Operat. Res"},{"key":"R26","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.ejor.2008.08.020","volume":"198","author":"Kenmochi","year":"2009","journal-title":"Europ. J. Oper. Res"},{"key":"R27","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1007\/s11750-010-0144-x","volume":"18","author":"Iori","year":"2010","journal-title":"TOP"},{"key":"R28","unstructured":"Johnson D.S., \nNear-Optimal Bin Packing Algorithms. Ph.D. thesis, \nMassachusetts Institute of Technology \n(1973)"},{"key":"R29","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0377-2217(02)00123-6","volume":"141","author":"Lodi","year":"2002","journal-title":"Europ. J. Oper. Res"},{"key":"R30","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/S0166-218X(01)00347-X","volume":"123","author":"Lodi","year":"2002","journal-title":"Discrete Appl. Math"},{"key":"R31","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1287\/ijoc.15.3.310.16082","volume":"15","author":"Martello","year":"2003","journal-title":"INFORMS J. Comput"},{"key":"R32","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/j.cor.2015.04.024","volume":"63","author":"Martello","year":"2015","journal-title":"Comput. Oper. Res"},{"key":"R33","unstructured":"Martello S. and \nToth P., \nKnapsack problems: Algorithms and computer implementations. \nJohn Wiley and Sons, \nChichester \n(1990)"},{"key":"R34","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/mnsc.44.3.388","volume":"44","author":"Martello","year":"1998","journal-title":"Manag. Sci"},{"key":"R35","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/ijoc.1060.0181","volume":"19","author":"Pisinger","year":"2007","journal-title":"INFORMS J. Comput"},{"key":"R36","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.ejor.2014.04.020","volume":"239","author":"Wei","year":"2014","journal-title":"Europ. J. Operat. Res"},{"key":"R37","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1016\/j.ejor.2014.12.048","volume":"243","author":"Wei","year":"2015","journal-title":"Eur. J. Oper. Res"},{"key":"R38","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1016\/j.ejor.2007.05.058","volume":"195","author":"Zachariadis","year":"2009","journal-title":"Europ. J. Oper. Res"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2017019\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T07:32:30Z","timestamp":1584689550000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2017019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4]]},"references-count":38,"journal-issue":{"issue":"2"},"alternative-id":["ro160064"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2017019","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4]]}}}