Model & Solution Strategy for Placement of Rectangular Blocks in the Euclidean Plane

This paper describes a nonlinear optimization model for the placement of rectangular blocks with some wire connections among them in the Euclidian plane, such that the total wire length is minimized. Such a placement algorithm is useful as a CAD tool for VLSI and PCB layout designs.

The mathematical model presented here ensures that the blocks will not overlap and minimizes the sum of the distances of the interconnections of the blocks with respect to their orientation as well as their position. We also present mechanisms for solving more restrictive placement problems, including one in which there is a set of equally spaced, discrete angles to be used in the placement. The mathematical model is based on the Lennard-Jones 6-12 potential equation, on a sine wave shaped penalty function, and on minimizing the sum of the squares of the Euclidian distances of the block interconnections. We also present some experimental results which show that good placements are achieved with our techniques.