In designing printed circuit boards, we are faced with the problem of positioning modules (typically integrated circuits) on the board. Desired criteria in a layout include (1) minimizing the area or aspect ratio of the board, so that it properly fits within the allotted space, and (2) minimizing the total or longest wire length in connecting the components. Circuit board placement is an example of the kind of messy, multicriterion optimization problems for which simulated annealing is ideally suited.

Formally, we are given a collection of a rectangular modules , each with associated dimensions . Further, for each pair of modules , we are given the number of wires that must connect the two modules. We seek a placement of the rectangles that minimizes area and wire-length, subject to the constraint that no two rectangles overlap each other.

The state space for this problem must describe the positions of each rectangle. To provide a discrete representation, the rectangles can be restricted to lie on vertices of an integer grid. Reasonable transition mechanisms including moving one rectangle to a different location, or swapping the position of two rectangles. A natural cost function would be

where , , and are constants governing the impact of these components on the cost function. Presumably, should be an inverse function of temperature, so after gross placement it adjusts the rectangle positions so they are distinct.

Simulated annealing performs well on such module placement problems. Indeed, a similar application appeared in the original paper on simulated annealing [KGV83]. More details on these and other applications appear in [AK89].

Mon Jun 2 23:33:50 EDT 1997