A Two-Stage Adaptive Search Algorithm for the 2-D Rectangle Packing Area Minimization Problem

This article studies the two-dimensional (2-D) rectangle packing area minimization problem (RPAMP), a key subproblem in floor planning for very large-scale integration (VLSI) chip design. The goal of RPAMP is to orthogonally pack a set of rectangles into a variable-sized rectangular container without overlap, while minimizing the area of the container. By transforming the original problem into a series of 2-D strip packing problems (2DSPs), we propose a two-stage adaptive search algorithm (TS-ASA) to tackle the RPAMP. TS-ASA incorporates several distinctive features: First, a new candidate width pruning strategy is introduced, which limits the number of rectangles used for width combinations, thus reducing the search space. Second, the packing process is divided into two stages, with distinct scoring rules for each stage to optimize space utilization. Additionally, a multirestart strategy is employed to identify the appropriate switching point for the scoring rules. Tested on 39 public benchmark instances and compared with existing state-of-the-art algorithms, TS-ASA improves the best-known solutions for 27 instances and matches the best results for two instances. The experimental results demonstrate the effectiveness and efficiency of the proposed TS-ASA. © 2013 IEEE.