{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:33:14Z","timestamp":1760707994735},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Artif. Intell. Tools"],"published-print":{"date-parts":[[2008,10]]},"abstract":"<jats:p> When handling 2D packing problems, numerous incomplete and complete algorithms maintain a so-called bottom-left (BL) property: no rectangle placed in a container can be moved more left or bottom. While it is easy to make a rectangle BL when it is added in a container, it is more expensive to maintain all the placed pieces BL when a rectangle is removed. This prevents researchers from designing incremental moves for metaheuristics or efficient complete optimization algorithms. This paper investigates the possibility of violating the BL property. Instead, we propose to maintain the set of maximal holes, which allows incremental additions and removals of rectangles. <\/jats:p><jats:p> To validate our alternative approach, we have designed an incremental move, maintaining maximal holes, for the strip packing problem, a variant of the famous 2D bin-packing. We have also implemented a metaheuristic, with no user-defined parameter, using this move and standard greedy heuristics. We have finally designed two variants of this incomplete method. In the first variant, a better first layout is provided by a hyperheuristic proposed by some of the authors. In the second variant, a fast repacking procedure recovering the BL property is occasionally called during the local search. <\/jats:p><jats:p> Experimental results show that the approach is competitive with the best known incomplete algorithms. <\/jats:p>","DOI":"10.1142\/s0218213008004205","type":"journal-article","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T11:50:07Z","timestamp":1225972207000},"page":"881-901","source":"Crossref","is-referenced-by-count":9,"title":["A STRIP PACKING SOLVING METHOD USING AN INCREMENTAL MOVE BASED ON MAXIMAL HOLES"],"prefix":"10.1142","volume":"17","author":[{"given":"BERTRAND","family":"NEVEU","sequence":"first","affiliation":[{"name":"INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, 06902 Sophia Antipolis cedex, France"}]},{"given":"GILLES","family":"TROMBETTONI","sequence":"additional","affiliation":[{"name":"INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, 06902 Sophia Antipolis cedex, France"}]},{"given":"IGNACIO","family":"ARAYA","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Universitad T\u00e9cnica Federico Santa Maria, Valparaiso, Chile"}]},{"given":"MARIA-CRISTINA","family":"RIFF","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Universitad T\u00e9cnica Federico Santa Maria, Valparaiso, Chile"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.07.004"},{"key":"rf2","series-title":"Studies on Computational Intelligence","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-79438-7_3","volume-title":"Adaptive and Multilevel Metaheuristics","volume":"136","author":"Araya I.","year":"2008"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1137\/0209064"},{"key":"rf4","first-page":"49","volume":"33","author":"Beasley J. E.","journal-title":"J. of the operational research society"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/25.3.353"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1987.70"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.11.016"},{"key":"rf8","first-page":"697","volume":"52","author":"Burke E.","journal-title":"Operations Research"},{"key":"rf10","first-page":"697","volume":"32","author":"Chazelle B.","journal-title":"IEEE Transactions on Computers"},{"key":"rf11","first-page":"115","volume":"6","author":"Chen D.","journal-title":"International Journal of Computer Science and Network Security"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2007.02.013"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00357-4"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0233-9_7"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.006"},{"key":"rf17","first-page":"1","volume":"10","author":"Lesh N.","journal-title":"ACM J. of Exp. Algorithmics"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.15.3.310.16082"},{"key":"rf19","first-page":"310","volume":"15","author":"Martello S.","journal-title":"Management science"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.01.009"}],"container-title":["International Journal on Artificial Intelligence Tools"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218213008004205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T02:28:12Z","timestamp":1565144892000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218213008004205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10]]},"references-count":18,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2008,10]]}},"alternative-id":["10.1142\/S0218213008004205"],"URL":"https:\/\/doi.org\/10.1142\/s0218213008004205","relation":{},"ISSN":["0218-2130","1793-6349"],"issn-type":[{"value":"0218-2130","type":"print"},{"value":"1793-6349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10]]}}}