Incremental move for strip-packing

Bertrand Neveu, Gilles Trombettoni, IGNACIO DANIEL ARAYA ZAMORANO

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

When handling 2D packing problems, numerous incomplete and complete algorithms maintain a so-called bottom-left (BL) property: every rectangle placed in a container is propped up bottom and left. While it is easy to make a rectangle BL when it is 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 only the set of "maximal holes", which allows incremental additions and removals of rectangles. 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 generic metaheuristic using this move and standard greedy heuristics. Experimental results show that the approach is competitive with the best known incomplete algorithms, especially the other metaheuristics (able to escape from local minima).

Original languageEnglish
Title of host publicationProceedings 19th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2007
Pages489-496
Number of pages8
DOIs
StatePublished - 1 Dec 2007
Event19th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2007 - Patras, Greece
Duration: 29 Oct 200731 Oct 2007

Publication series

NameProceedings - International Conference on Tools with Artificial Intelligence, ICTAI
Volume2
ISSN (Print)1082-3409

Conference

Conference19th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2007
CountryGreece
CityPatras
Period29/10/0731/10/07

Fingerprint Dive into the research topics of 'Incremental move for strip-packing'. Together they form a unique fingerprint.

Cite this