How to include safety distance in only one direction, when solving a facility layout problem using a mixed-integer programming approach?

Question

I'm trying to design an office using a mixed-integer programming approach, but I'm having some trouble.

Task: Place a fixed number of rectangular shaped tables in a rectangular shaped room. If we consider the room as being in the first quadrant of a coordinate system, we will have the lower left corner of the room in origin $(0,0)$. The dimensions of the room are: $X_{max}$ $\times$ $Y_{max}$.

The tables should be able to rotate 90 degrees. A table has two parallel sides of length $\alpha$ and two parallel sides of length $\beta$. $\alpha > \beta$.

Table $i$ and table $j$ can be placed in four different ways.

1. Table $i$ has a side of length $\alpha$ facing a side of table $j$ of length $\alpha$
2. Table $i$ has a side of length $\alpha$ facing a side of table $j$ of length $\beta$
3. Table $i$ has a side of length $\beta$ facing a side of table $j$ of length $\alpha$
4. Table $i$ has a side of length $\beta$ facing a side of table $j$ of length $\beta$

One of a table $i$'s $\alpha$-sides has to keep a minimum distance to all other tables. This is the side of the table where a person has to sit. Due to work regulations there has to be a safety distance, $safe\_dist$, between this person's back and other people or furniture.

So far my MIP looks like this:

$\#$ Sets

$I$: set of tables

$\#$ Binary variables

x coordinate of the geometrical centre of item $i$

$x_i\ge 0, \forall i \in I$

x coordinate of the geometrical centre of item $i$

$y_i\ge 0, \forall i \in I$

length of item $i$

$l_i\ge 0, \forall i \in I$

depth of item $i$

$d_i\ge 0, \forall i \in I$

1 if length of item $i$ is equal to $\alpha_i$; 0 otherwise

$O_i \in \{0,1\}, \forall i \in I$

non-overlapping binary, a set of values which prevents equipment overlap in one direction in the $x$-$y$ plane

$E1_{ij}, E2_{ij} \in \{0,1\}, \quad \forall i, j\in I, j>i$

$\#$ Constraints

Layout design constraints to ensure that tables are placed within the boundaries of the room:

$x_i \ge \frac{l_i}{2}, \forall i\in I$

$y_i \ge \frac{d_i}{2}, \forall i\in I$

$x_i + \frac{l_i}{2}\le X_{max}, \forall i\in I$

$y_i + \frac{d_i}{2}\le Y_{max}, \forall i\in I$

Rotation constraints:

$l_i = \alpha_iO_i + \beta_i(1-O_i), \forall i \in I$

$d_i = \alpha_i + \beta_i - l_i, \forall i \in I$

Non-overlapping constraints:

$x_i-x_j + BM(E1_{ij}+E2_{ij})\ge \frac{l_i+l_j}{2}, \quad \forall i,j\in I, j>i$

$x_j-x_i + BM(1-E1_{ij}+E2_{ij})\ge \frac{l_i+l_j}{2}, \quad \forall i,j\in I, j>i$

$y_i-y_j + BM(1+E1_{ij}-E2_{ij})\ge \frac{d_i+d_j}{2}, \quad \forall i,j\in I, j>i$

$y_j-y_i + BM(2-E1_{ij}-E2_{ij})\ge \frac{d_i+d_j}{2}, \quad \forall i,j\in I, j>i$

, where $BM$ is a very large number.

I'm aware that if I add $safe\_dist$ to the rhs of the last four constraints, I ensure that there is kept a minimum distance to other tables from both $\alpha$-sides and $\beta$-sides of table $i$, which is way too much. So the question is how do I include the safety distance from only one $\alpha$-side of table $i$ and is it possible to do it with linear constraints only?

Appreciate your help! Please ask if anything is unclear :)

Answer 1

You need to involve $O_i$ in the desired constraint. I would recommend that you first express the rule as a logical proposition of the form “if $O_i=1$ and $O_j=1$ and $E1_{ij}=1$ and ... then ... $\ge$ safedist”