Placement Problems

The rigorous definition of the problem begins with a set $\mathcal{O}$ of $|\mathcal{O}|$ objects to place:

$$\begin{equation} \mathcal{O}=\{o_{i}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{O}|\label{eq: 2Dproblem1} \end{equation}$$

Each object $o_{i}$ has a shape $s_{i}$, a set $\mathcal{A}_{i}$ of $|\mathcal{A}_{i}|$ arrangements of possible orientations and a set $\mathcal{T}_{i}$ of $|\mathcal{T}_{i}|$ terminals:

$$\begin{equation} o_{i}=\{s_{i},\mathcal{A}_{i},\mathcal{T}_{i}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{O}|\label{eq: Defei} \end{equation}$$

$$\begin{equation} \mathcal{A}_{i}=\{a_{ij}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{O}|\,;\,\forall\,j=1,\cdots,|\mathcal{A}_{i}|\label{eq: 2Dproblem2} \end{equation}$$

$$\begin{equation} \mathcal{T}_{i}=\{t_{ij}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{O}|\,;\,\forall\,j=1,\cdots,|\mathcal{T}_{i}|\label{eq: 2Dproblem3} \end{equation}$$

All the terminals also included in the set $\mathcal{T}$:

$$\begin{eqnarray} \mathcal{T}=\{t_{t}\} & & \forall\,t=1,\cdots,|\mathcal{T}| \end{eqnarray}$$ where $\mathcal{T}$ also include some fixed terminals not assigned to an object.

Each terminal $t_{t}$ has a set $\mathcal{C}_{t}$ of $|\mathcal{C}_{t}|$ possible connectors (positions) on the corresponding element:

$$\begin{equation} C(t_{t})=\mathcal{C}_{t}=\{c_{tk}\}\quad\quad\forall\,k=1,\cdots,|\mathcal{T}|\label{eq: 2Dproblem4} \end{equation}$$

The positions are relative to a given orientation of an element, i.e. an unique $c_{tk}$ variable represents all the possible coordinates for the different orientations of the corresponding element.

A set $\mathcal{N}$ of $|\mathcal{N}|$ nets are given, where each net $n_{i}$ is defined by a weight $w_{i}$ and by a sub-set $\mathcal{U}_{i}$ from $\mathcal{T}$ of $|\mathcal{U}_{i}|$ terminals:

$$\begin{equation} \mathcal{N}=\{n_{i}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{N}|\label{eq: 2Dproblem5} \end{equation}$$ $$\begin{equation} n_{i}=\{w_{i},\mathcal{U}_{i}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{N}|\label{eq: 2Dni} \end{equation}$$

$$\begin{equation} \mathcal{U}_{i}=\{u_{ij}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{N}|\,;\,\forall\,j=1,\cdots,|\mathcal{U}_{i}|\,;\,u_{ij}\,\epsilon\,\mathcal{T}\label{eq: 2DUi} \end{equation}$$

The global layout has to fit in given size limits $(x_{max},y_{max})$. A set $\mathcal{C}$ of $|\mathcal{C}|$ constraints between the elements exists also:

$$\begin{equation} \mathcal{C}=\{c_{i}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{C}|\label{eq: 2Dproblem6} \end{equation}$$

To problem is to fix a set of variables for the objects and the nets. Concerning the elements, the variables to be determined are the position and the orientation (the $v$ stands for variable):

$$\begin{equation} o_{i}^{v}=\{x_{i},y_{i},a_{i}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{O}|\label{eq: 2Devi} \end{equation}$$

For the nets, it is necessary to determine the configuration, i.e. the pairs of terminals and their connector which minimize the length of the corresponding net. This amounts to determine a set $\mathcal{U}_{i}^{v}$ of $u_{i}^{v}$ pairs of terminal connectors (the $v$ stands for variable), each pair is defined by two terminals, and each terminal is defined by a given connector:

$$\begin{equation} \mathcal{U}_{i}^{v}=\{u_{ij}^{v}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{N}|\,;\,\forall\,j=1,\cdots,|\mathcal{U}_{i}^{v}|\label{eq: 2DUvi} \end{equation}$$

$$\begin{equation} u_{ij}^{v}=\{t_{ijk}^{v},t_{ijk}^{v}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{N}|\,;\,\forall\,j=1,\cdots,|\mathcal{U}_{i}^{v}|\,;\,\forall\,k=1,2;\,t_{ijk}^{v}\,\epsilon\,\mathcal{U}_{i}\label{eq: 2Duvij} \end{equation}$$

$$\begin{equation} t_{ijk}^{v}=\{c_{ijk}^{v}\}\quad\quad\forall\,i=1,\cdots,|\mathcal{N}|\,;\,\forall\,j=1,\cdots,|\mathcal{U}_{i}^{v}|\,;\,\forall\,k=1,2;\,c_{ijk}^{v}\,\epsilon\,C(t_{ijk}^{v})\label{eq: 2Dtvijk} \end{equation}$$

We suppose that all the positions and the sizes are integers. In practice, with a good scale choice, this condition can always be respected. The fact that integer values are used, i.a. that the positions and the sizes only take a finite set of distinct values, makes the 2D Problem a combinatorial optimization problem.

Each object may have multiple orientations obtained by $90^{\circ}$ rotations and flips. The different possible orientations are showed at Figure 1↓. As explained, the number of the orientations allowed has to be fixed for all the objects to place.

The limitation to these orientations is justified by the fact that the union of a given set of rectangular polygons with one of these orientations is also a rectangular polygon (Figure 2↓a), which makes it easy to consider it as an object itself. In comparison, the union of two rectangular polygons where one of them was obtained by a $45^{\circ}$ rotation (Figure 2↓b) is not a rectangular polygon.

A terminal can be localized in a single point or have different positions called connectors, as in the VLSI problem.

When the instance defines terminals, every object involved must have at least one terminal with one connector. By default, when an object defines no terminals, an imaginary one is created at a “central” position $C$ of the corresponding object. When the object is a rectangle, the “central” position $C$ is the mass point $G$ of the rectangle (Figure 3↓a), else the “central” position $C$ corresponds to the nearest vertex to the mass point $G$ of the bounding rectangle (Figure 3↓b).

Furthermore, terminals may also be fixed and representing links between the layout that have to be produced and “others layouts”. By example, for the VLSI problem, when the layout is representing a macro-cell with terminals needed for external connectivity (Figure 4↓).

When a net links more than two objects, it does not mean that all terminals involved have to be connected together directly. This means that there are different orientations possible for a single net. The Figure 5↓ shows the different configuration for a net between three objects. Of course, the number of possibilities increases when some terminals may have multiple connectors.

The “closeness” between two objects is not only given by their geometrical information, but also by length of the nets. It is thus necessary to evaluate the length of a given net, which means that a specific configuration for that net must be fixed. The length of the net is then the product of the weight of this net with the sum of the geometric distance between the different connectors of the terminals used.

To evaluate the geometric distance of two positions, the Manhattan distance is used. Figure 6↓ shows the Manhattan distance between two positions A and B, which is the length of the two lines.

The problem with the nets is that a given net can have multiple configurations for the position of the terminals involved and the different parts that will be used. To solve this problem, it is necessary to briefly introduces some concepts from the graph theory. There are complete dedicated books to the graph theory [1, 2].

When removing edges and/or vertices from a given graph $G$, a subgraph of $G$ is obtained. During the construction of a graph, when a vertex is removed, all the edges connected to it must also be removed.

Two vertices $u$ and $v$ are connected if there is an edge starting from vertex $u$ and finishing at vertex $v$. If all pairs of vertices in a graph are connected, the graph is called a connected graph. When a direction is associated with the edges of the graph, the graph is called a directed graph, otherwise it is called an undirected graph.

A path is a sequence of alternating vertices and edges which starts and finishes with a vertex. The length of the path is the number of edges it contains. Note that a given graph can have a length of zero. When a path starts and finishes with the same vertex with a length greater than zero, it is called a cycle. A path or a cycle not containing two or more occurrences of the same vertex is called a simple path or cycle.

A tree is a connected graph without cycles. A spanning tree of a connected graph is a subgraph which is a tree and that contains all vertices of the corresponding graph. In the case of edge-weighted undirected graphs, there is a spanning tree with the least total edge weight, which is the minimum spanning tree. Figure 7↓ shows a graph and the corresponding minimum spanning tree.

One of the algorithm proposed to solve the minimum spanning tree problem is described in [3]. The algorithm starts with an arbitrary vertex which is considered the initial tree. Besides it is assumed that a vertex has the attribute $distance$ and $via-edge$. The first one is used to register the shortest distance from a vertex not yet in the tree to a vertex already selected. The second one represents the edge through which this shortest connection is made. In each iteration, the vertex with the minimal $distance$ value is added to the tree together with the edge of its $via-edge$ attribute. Then the values of the $distance$ and $via-edge$ attributes are updated for the vertices not yet in the tree. Of course, the algorithm stops when all vertices are in the tree.

An example of the correspondence is shown at Figure 8↑. Suppose we have three objects with a single terminal, each terminal has two possible positions. To construct the graph which corresponds to the net involving the terminals $A$, $B$ and $C$, we create a vertex for each terminal and an edge between all these vertices. The weight of a given edge, for example between the vertices $A$ et $B$, is the minimum distance of all possible distances between the positions of these two terminals, in this example, it is the distance between the positions $P_{a1}$ and $P_{b1}$.

Once the corresponding graph is constructed, the minimum spanning tree is searched. In the above example, if we suppose that the greatest distance is $d(P_{c2},P_{b2})$, the result is shown at Figure 9↓ (the distance used is the Manhattan distance).

The length of the net is then given by ↓:

$$\begin{equation} L_{net}=weight\cdot\left(d(P_{a1},P_{b1})+d(P_{a2},P_{c1})\right)\label{eq: netlen} \end{equation}$$

Sometimes, it is necessary to compute the partial length of a given net, i.a. the length of the net where only the already placed objects are considered. To compute this partial net, a subgraph is constructed with only the already placed objects, and the same method is then used.

The “fixed constraints” $C_{f}$ constitute the first class, where a set of objects must be placed in fixed relative positions and orientations. A typical example of such a constraint in the VLSI problem is the amplificator, which is constructed by using two transistors, the relative positions and orientations of these transistors depends directly from the characteristics of the amplificator.

The “maximum constraints” $C_{max}$ are the second class, where a set of objects has to be place at a maximal distance of another set of objects. In the case of the VLSI problem, some nets are critical and cannot exceed some length, meaning that the objects involved have to be close.

The “minimum constraints” $C_{min}$ are the last class, where a set of objects has to be place at a minimal distance of another set of objects. Again to take the VLSI problem as example, objects that release heavy heat must be placed far from each other to balance the heat repartition of the resulting placement.

In fact, this is not a simple task since the quality of a solution relies on two criteria: the area occupied and the connection lengths. One algorithm can outperform the “ideal” solution with regard to one of the criteria by producing a bad solution regarding the second criteria. So, if it is possible to compare the value of both criteria for the “ideal” and the “computed” solution, the evaluation depends on the preferences of the particular instance of a given problem.