An Exact Method for Area Minimization in Planar Integrated Circuit Floorplanning

To address the rectangular packing area minimization problem (RPAMP) in integrated circuit floorplanning and improve circuit performance, a two-stage exact algorithm based on macro problem transformation is proposed. The RPAMP is reformulated as a series of two-dimensional strip packing problems (SPP) for solution. In the first stage, an adaptive selection strategy is employed to set the width of RPAMP to the candidate width corresponding to the minimum-area lower bound, thereby converting the problem into a series of SPPs. In the second stage, an exact solution algorithm based on Benders′ decomposition is proposed to solve the SPP. Specifically, by fixing the height of strips, the problem is transformed into a two-dimensional rectangle packing problem (RPP). Then, the RPP is decomposed into a master problem and subproblems, and cutting planes are added iteratively to approximate the optimal solution. If the RPP is infeasible, the current lower bound of the strip height is recorded, and a new candidate width is selected for iteration until the optimal solution to the RPAMP is found. Experimental results show that the proposed method can find the optimal solution for small to medium-sized instances within reasonable computational time. In particular, for instance n10, it derives a better solution than that obtained in the literature.