Hierarchical Rectangle Packing Solved by Multi-Level Recursive Logic-based Benders Decomposition
Preprint
Abstract
We study the two-dimensional hierarchical rectangle packing problem, motivated by applications in analog integrated circuit layout, facility layout, and logistics. Unlike classical strip or bin packing, the dimensions of the container are not fixed, and the packing is inherently hierarchical: each item is either a rectangle or a block occurrence, whose dimensions are a solution of another packing problem. This recursive structure reflects real-world scenarios in which components, boxes, or modules must be packed within higher-level containers. We formally define the problem and propose exact formulations in Mixed-Integer Linear Programming and Constraint Programming. Given the computational difficulty of solving complex packing instances directly, we propose decomposition heuristics. First, we implement an existing Bottom-Up baseline method that solves subblocks before combining them at higher levels. Building upon this, we introduce a novel multilevel Logic-based Benders Decomposition method. This heuristic method dynamically refines block dimension constraints, eliminating the need for manual selection of candidate widths or aspect ratios. Experiments on synthetic instances with up to seven hierarchy levels, 80 items per block, and limited computation time show that the proposed decomposition significantly outperforms both monolithic formulations and the Bottom-Up method in terms of solution quality and scalability.Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Exact algorithms in bar nesting: How to cut general items from linear stocks so that wastage is minimisedComputers & Industrial Engineering, 2024
- ViolationLS: Constraint-Based Local Search in CP-SAT2024
- Metaheuristics for bilevel optimization: A comprehensive reviewComputers & Operations Research, 2023
- A branch-and-price algorithm for the temporal bin packing problemComputers & Operations Research, 2020
- Logic based Benders' decomposition for orthogonal stock cutting problemsComputers & Operations Research, 2017
- Models and algorithms for packing rectangles into the smallest squareComputers & Operations Research, 2015
- The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratioComputers & Operations Research, 2009
- Optimal rectangle packingAnnals of Operations Research, 2008
- A branch and bound algorithm for the strip packing problemOR Spectrum, 2008
- An analytical model for the container loading problemEuropean Journal of Operational Research, 1995