TY - GEN
T1 - Almost square packing
AU - Simonis, Helmut
AU - O'Sullivan, Barry
PY - 2011
Y1 - 2011
N2 - The almost square rectangle packing problem involves packing all rectangles with sizes 1 ×2 to n ×(n+1) (almost squares) into an enclosing rectangle of minimal area. This extends the previously studied square packing problem by adding an additional degree of freedom for each rectangle, deciding in which orientation the item should be packed. We show how to extend the model and search strategy that worked well for square packing to solve the new problem. Some adapted versions of known redundant constraints improve overall search times. Based on a visualization of the search tree, we derive a decomposition method that initially only looks at the subproblem given by one of the cumulative constraints. This decomposition leads to further modest improvements in execution times. We find a solution for problem size 26 for the first time and dramatically improve best known times for finding solutions for smaller problem sizes by up to three orders of magnitude.
AB - The almost square rectangle packing problem involves packing all rectangles with sizes 1 ×2 to n ×(n+1) (almost squares) into an enclosing rectangle of minimal area. This extends the previously studied square packing problem by adding an additional degree of freedom for each rectangle, deciding in which orientation the item should be packed. We show how to extend the model and search strategy that worked well for square packing to solve the new problem. Some adapted versions of known redundant constraints improve overall search times. Based on a visualization of the search tree, we derive a decomposition method that initially only looks at the subproblem given by one of the cumulative constraints. This decomposition leads to further modest improvements in execution times. We find a solution for problem size 26 for the first time and dramatically improve best known times for finding solutions for smaller problem sizes by up to three orders of magnitude.
UR - https://www.scopus.com/pages/publications/79956302597
U2 - 10.1007/978-3-642-21311-3_19
DO - 10.1007/978-3-642-21311-3_19
M3 - Conference proceeding
AN - SCOPUS:79956302597
SN - 9783642213106
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 196
EP - 209
BT - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 8th International Conference, CPAIOR 2011, Proceedings
T2 - 8th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2011
Y2 - 23 May 2011 through 27 May 2011
ER -