## 2 Facility Layout Problem with Relative Positioning Constraints
### The FLPRC Formulation  
We consider \(N\) departments \(i=1,\cdots,N\), which have centroid positions \((x_{i},y_{i})\in\mathbb{R}^{2}\) and shapes \((w_{i},h_{i})\in\mathbb{R}^{2}\) of half of their widths and heights, for \(i=1,...,N\). They must be placed in a rectangle area with width \(W\) and height \(H\), and lower left corner at the position \((0,0)\), under specified relative positioning.  
The objective of FLP is to find a set of positions and shapes of department \(r_{i}=[x_{i},y_{i},w_{i},h_{i}]^{\mathrm{T}}\) that yield as small material handling costs as possible. In the FLP2, the material handling cost is measured as the product of distance times flows between departments as in (1)  
\[\mathrm{minimize}\quad\sum_{i=1}^{N}\sum_{j=i+1}^{N}f_{ij}d_{ij}, \tag{1}\]  
where \(f_{ij}\) denotes the material flows from department \(i\) to department \(j\) and \(d_{ij}\) denotes the distance between centroids of department \(i\) and department \(j\). The choices of distance measures are usually either rectilinear or Euclidean, but, in the FLP2, the rectilinear distances are used as in (2).  
\[\begin{array}{ll}d_{ij}&=d_{ij}^{x}+d_{ij}^{y}\\ &=|x_{i}-x_{j}|+|y_{i}-y_{j}|\end{array} \tag{2}\]  
The absolute values in the distance function (2) can be linearized as in (3)  
\[\begin{array}{ll}-d_{ij}^{x}\leq x_{i}-x_{j}\leq d_{ij}^{x}\\ -d_{ij}^{y}\leq y_{i}-y_{j}\leq d_{ij}^{y}\end{array} \tag{3}\]  
We call these inequalities the _distance constraints_.  
In the FLP, it is required that the departments lie inside the bounding rectangle with width \(W\) and height \(H\) as in (4) and (5).  
\[w_{i}\leq x_{i}\leq W-w_{i}, i=1,\cdots,N \tag{4}\] \[h_{i}\leq y_{i}\leq H-h_{i}, i=1,\cdots,N \tag{5}\]  
These inequalities are called the _within-boundary constraints_.  
The _aspect-ratio constraints_ require that the aspect ratio of a department is bounded within upper and lower limits, i.e.,  
\[l_{i}\leq h_{i}/w_{i}\leq u_{i}, i=1,\cdots,N, \tag{6}\]  
where aspect ratio of a department is defined by \(h_{i}/w_{i}\) and the upper and lower bound of aspect ratio are defined by \(u_{i},l_{i}\), respectively. Multiplying both sides of each inequality by \(w_{i}\) reduces to these constraints into linear inequalities as in (7).  
\[l_{i}w_{i}\leq h_{i}\leq u_{i}w_{i}, i=1,\cdots,N, \tag{7}\]  
In case the dimension of a department is known a priori (often called Machine Layout Problem, or MLP), we can use the fixed aspect ratio with \(l_{i}=u_{i}\), which results in a linear equality constraint.  
Let \(s_{i}\) be the quarter of minimal area of department \(i\) for \(i=1,...,N\), thus the _area constraints_ require Equation (8):  
\[w_{i}h_{i}\geq s_{i}, i=1,\cdots,N. \tag{8}\]Instead of these exact constraints, we use an outer polyhedra approximation, proposed by [40], to obtain the speed-up as (9):  
\[s_{i}w_{i}+4\varpi_{im}^{2}h_{i}\geq 2s_{i}\varpi_{im},\qquad\quad i=1,\cdots,N,m=1,\cdots,M. \tag{9}\]  
where affine support points are defined by \(\varpi_{im}\) and the number of affine support points are defined by \(M\), respectively. By using the constraints (9), instead of (8), the area constraints can be reduced to the standard linear inequalities, and thus can be solved much faster.  
The relative-positioning constraints require that, for each pair of departments \((i,j)\) with \(i\
eq j\), the department \(i\) must be placed to the left, right, above, or below the department \(j\). These relations are specified with the binary variables \(\mathcal{H}\) (meaning 'horizontal') and \(\mathcal{V}\) (meaning'vertical') as in (10) and (11):  
\[\mathcal{H}_{ij} = \left\{\begin{array}{ll}1&\quad(\text{if $i$ is left of $j$})\\ 0&\quad(\text{\emph{otherwise}})\end{array}\right.\] (10) \[\mathcal{V}_{ij} = \left\{\begin{array}{ll}1&  
* \(d^{x}_{ij}\,d^{y}_{ij}\): rectilinear distance between department \(i\) and \(j\) in \(x\) and \(y\) direction;
* \(x_{i},y_{i}\): \(x\) and \(y\) coordinates of centroid of department \(i\);
* \(w_{i},h_{i}\): half length of width and height of department \(i\);