Dynamic reduction heuristics for the rectangle packing area minimization problem

The rectangle packing area minimization problem is a key sub-problem of floorplanning in VLSI design. This problem places a set of axis aligned two-dimensional rectangular items of given sizes onto a rectangular plane such that no two items overlap and the area of the enveloping rectangle is minimized. This paper presents a dynamic reduction algorithm that transforms an instance of the original problem to a series of instances of the rectangle packing problem by dynamically determining the dimensions of the enveloping rectangle. We define an injury degree to evaluate the possible negative impact for candidate placements, and we propose a least injury first approach for solving the rectangle packing problem. Next, we incorporate a compacting approach to compact the resulting layout by alternatively moving the items left and down toward a bottom-left corner such that we may obtain a smaller enveloping rectangle. We also show the feasibility, compactness, non-inferiority, and halting properties of the compacting approach. Comprehensive experiments were conducted on 11 MCNC and GSRC benchmarks and 28 instances reported in the literature. The experimental results show the high efficiency and effectiveness of the proposed dynamic reduction algorithm, especially on large-scale instances with hundreds of items.