Abstract:This paper addresses an NP-hard layout optimization problem with a high computational complexity: the two-dimensional rectangle packing area minimization problem (RPAMP), which is a core issue of floorplanning problem in the very-large-scale integration (VLSI) design. First, by dynamically designing the two dimensions of the large rectangular frame, the study reduces the solving of a RPAMP to the solving of a series of two-dimensional rectangle packing decision problems (RPDP). Then, based on a best-fit-degree approach for the RPDP, the designs a least-damage-first algorithm for the RPDP, which further takes the consideration of the current placement's impact on global compaction and of its negative effect on local space's integrity. Next, by combining the method of dynamically designing two dimensions of the rectangular frame, a final dynamic reduction algorithm is proposed for solving the RPAMP. Experiments were on 15 RPAMP instances (including the well-known MCNC instances and GSRC instances). Computational results show that the proposed algorithm refreshed the current best solutions on nine instances. At the same time it also matchs the current best records on two other instances. The obtained average filling rate is 98.50%, which improved the current best results reported in the literature by 0.85%.