Linear constraint

Question

I found this video extremely helpful to determine the floorplanning constraints.

The first two constraints (i) make sure the modules are within the feasible floorplan; the subsequent four constraints (ii) make sure that no two modules overlap, and the last constraint (iii) describes all the modules in the first quadrant.

My goal is a bit different- I am not sure if just the mentioned constraints can be modified for this purpose. Basically for area minimization- each module is divided into 4 sections (1, 2, 3, 4 in the picture) and specific portions of the sections (labeled red) need to be a minimum distance, D away from other modules' red portions as shown in the example on the left. For example, portions 2, and 4 of a module need to be D away from other modules 2, and 4 portions. In this way, some more floorplan areas can be minimized compared to doing it with the whole modules (shown on the right).

Any advice on the modification of the (i, ii, iii) constraints in order to achieve my goal would be helpful.

Answer 1

The constraints cannot be modified in the manner you suggest. You are trying to include a distance constraint based on the L2-norm (Euclidean distance) between specific points of modules. The expression for the distance between two points is a nonlinear function of the decision variables. This cannot be expressed in the form of a linear constraint, even when you allow for integer decision variables.

You have a number of options:

1. Formulate a nonlinear program and try to solve it. I suspect such a formulation would be non-convex, and thus difficult to solve for large instances. So, unless your instance of the problem is small, this would likely be intractable.
2. Develop an efficient heuristic solution. This is an attempt to find a good, although not provably optimal, solution to the above non-linear program. This is the practical approach most people take.
3. Use approximations. If it is possible to constrain your modules to fall on specific grid points, then it is possible to calculate the distance between all pairs of grid points. This can be formulated as a mixed linear program.
4. Use an approximate distance. Rather than using the L2-norm, you might consider using the L1-norm. Unlike L2 norms, L1 norms can be modeled using linear constraints.

Answer 2

I agree that the $L_2$ norm is off the table, because it creates a nonconvex quadratic constraint. Unfortunately, given the base model (and in particular the choice of binary variables), I'm not sure it would be practical to use the $L_1$ norm either.

The problem with $L_1$ lies in the absolute values, which need to be linearized. There are essentially three ways to handle $\vert u - v\vert$ in a MIP model. The first is easy: if you know that $u > v$, the absolute value is $u-v$, and otherwise it is $v-u$. The problem here is that you don't reliably know the signs of the coordinate differences between modules. For instance, if $x_{ij} = 0 = y_{ij}$, you know that $j$ is to the right of $i$, but you don't know if it is above/alongside/below $i$. The second linearization technique is to use an auxiliary variable $w$ with the constraints $w\ge u - v$ and $w\ge v - u$, which implies $w\ge \vert u-v\vert$. This would be fine if your norm constraint were $\parallel \dots \parallel \le D$, but because it is a greater-than constraint, the model would be tempted to "lie" (e.g., $u=1$, $v=1$, $w=D > 1$). The third approach involves throwing in additional binary variables, one for each absolute value, along with additional defining constraints, which I think would be a huge headache to formulate and would result in a very large model.

A more tractable approach might be to use the $L_\infty$ norm (known in some circles as the "sup" norm). For each pair $i$, $j$ of modules, you need to consider all four possible combinations of $x_{ij}$ and $y_{ij}$. I'll demonstrate one case (the one depicted in your diagram) and leave the others as an exercise for the reader. Suppose we have $x_{ij}=0=y_{ij}$, meaning $i$ is left of $j$, as in the diagram. There are four combinations of a red block from $i$ and a red block from $j$. A sufficient condition that all four are separated by at least $D$ in the $L_\infty$ norm is that the left edge of $j$ is at least $D$ units to the right of the right edge of $i$. Note that this condition is sufficient but not necessary, since $j$ could be closer to $i$ horizontally but, if we slid $j$ up or down enough, further than $D$ from $i$ in the sup norm. To enforce the sufficient condition, we add the constraint $$x_j - (x_i + w_i) \ge D(1-x_{ij}-y_{ij}).$$

Because the approach is "conservative", this might be too wasteful of space, but it is easy to add to the existing model.

I should note that I am assuming all modules have the same layout (blocks 2 and 4 red, 1 and 3 not). If, for instance, module $i$ was as depicted but module $j$ had only blocks 1 and/or 4 red, the left side of the constraint above would become $$\left( x_j + \frac{w_j}{2}\right) - \left( x_i + w_i \right).$$

Update: Sticking to the $L_\infty$ norm, I think there is a way to reduce wasted space (but not eliminate it entirely), at a cost in computational complexity. Whether the trade-off is worthwhile is, to me, an empirical question.

The approach is as follows. First, in addition to continuous variables for the coordinates of the lower left corner of each module, add continuous variables for the lower left corner of each red block, along with linear equations defining the block corners in terms of the module corners. This much is "cheap".

Next, redefine the binary variables to apply to individual red blocks, as well as modules. Since you are going from two binary variables per pair of modules to two per pair of blocks, and there are four times as many block pairs as module pairs, this will quintuple the number of binary variables, as well as the number of distance-related constraints. (The no-overlap constraints can still be enforced at the module level, so no change there.) If $D$ is large enough relative to the module dimensions, you may not need the original binary variables and the no-overlap constraints (because keeping red blocks more than $D$ apart would preclude module overlap), but my guess is you will need to keep the original binaries and their constraints.