Abstract:
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. This approach reformulates the RPAMP as a series of two-dimensional strip packing problems (SPP) for solution. In the first stage, an adaptive selection strategy is employed to fix the width of RPAMP to the candidate width corresponding to the minimum area lower bound, thereby converting the problem into a series of strip packing problems. In the second stage, an exact solution algorithm based on Benders′ decomposition is proposed to solve the strip packing problem. First, by fixing the height of the strips, the problem is transformed into a two-dimensional rectangle packing problem (RPP). Then, the RPP is decomposed into a master problem and subproblems, with cutting planes 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 iterative computation 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 a reasonable time, especially for the instance n10, where a better solution than that in the literature was found.