Hierarchical rectangle packing solved by multi-level recursive logic-based benders decomposition
研究二维分层矩形装箱问题，提出多级逻辑型Benders分解启发式方法，在模拟集成电路布局等场景中，相比传统方法显著提升求解质量和可扩展性。
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 dimension constraints of block types, 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 type, 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.