Sparsity pattern


OrginatorUniversity of Washington Electrical Engineering Dept.
FormulatorXiaowen Liu
DonatorEd Klotz, ILOG
Integer ObjectiveUnknown
LP Objective3.46000000e+02
Root LP Basisliu.bas.gz
Set partitioning
Set packing
Set covering
Equality Knapsacks
Bin packing
Invariant Knapsack
Integer Knapsack
Upper bounds
Lower bounds
Mixed 0/12178
General Cons.

The model involves the floorplan and placement problem in the physical design of VLSI circuits. The floorplan and placement is to place a set of rectangular modules(or blocks) on a chip. we know the initial topology of the modules, and want to locally swap the modules and/or orientate the modules such that the total area of the chip is minimized and there is no overlaps between between any two modules.

We are trying to use Integer Programming to optimize the area. The problem formulation is described in the following.

To prevent overlapping of modules i and j, it is required that at least one of the following linear inequalities holds:

xi + wi ≤ xj; /* i is to the left of j */
xi - wj ≥ xj; /* i is to the right of j */
yi + hi ≤ yj; /* i is below j */
yi - hj ≥ yj; /* i is abover j */ (1)
where xi, yi, xj, yj is the continuous variables denote the position of the lower left corners of the modules i and j with respect to the center of coordinates. wi, hi is the width and height of module i, which is known values.

In order to ensure that at least on of above inequalities always holds we introduce two 0-1 integer variables xxixj and yyiyj, now we consider the following system of linear inequalities for any pair of modules i and j:

xi + wi ≤ xj + W ( xxixj + yyiyj);
xi - wj ≥ xj - W (1 - xxixj + yyiyj);
yi + hi ≤ yj + H (1 + xxixj - yyiyj);
yi - hj ≥ yj - H (2 - xxixj - yyiyj); (2)
where W = Σwi, H = Σhi.

Assume that x* and y* are the final width and height of the chip, we need to optimize the area x* times y*. If we know the range of the aspect ratio of x* and y* to be 0.85 to 1.15, we can linearize the quadratic problem to a linear problem:

Minimize: 0.495 x* + 0.5014 y*

The additional constraints are:
xi ≥ 0, yi ≥ 0,
x* ≥ xi + wi,
y* ≥ yi + hi, for all modules. (3)

The above is the first formulation of our problem. In order to achieve better floorplan, we allow the rotation of the blocks by introduce another 0-1 integer variable zi, where zi = 0 when i block is placed in its initial orientation and zi = 1 when block i is rotated 90 degree. The constraints (1) is rewritten in the following form:

xi + zihi + (1-zi)wi ≤ xj + M(xxixj + yyiyj);
xi - zjhj - (1-zj)wj ≥ xj - M(1 - xxiyj + yyiyj);
yi + ziwi + (1-zi)hi ≤ yj + M(1 + xxixj - yyiyj);
yi - zjwj - (1-zj)hj ≥ yj - M(2 - xxiyj - yyiyj); (4)

and the constraints (3) is rewritten as:

xi ≥ 0, yi ≥ 0,
xi + (1 - zi)wi + zihi ≤ x*,
yi + ziwi + (1 - zi)hi ≤ y*, for all modules (5)

Because we have the initial topology of the modules, we only allow the local modules to swap. So to local module pairs they have constraints (4), where there are two integer variables to ensure nonoverlapping. To the modules are very far away, their topology is fixed, which means these pairs of modules need only one of inequalities of (1) to guarantee the non- overlapping.

Last Update : 2010/06/09 13:56:11 $ by Gerald Gamrath
© 2010 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)