5.3 Layout on Several Floors
79
1 ≤ i < j ≤ n, n + 1 ≤ ≤ n + e
x i +
1
2
w i ≤
1
2
w F , x i −
1
2
w i ≥ −
1
2
w F , 1 ≤ i ≤ n + e
(5.14)
y i +
1
2
h i ≤
1
2
h F , y i −
1
2
h i ≥ −
1
2
h F , 1 ≤ i ≤ n + e
(5.15)
w i h i ≥ A i , 1 ≤ i ≤ n
(5.16)
w i − βh i ≤ 0, h i − βw i ≤ 0, 1 ≤ i ≤ n
(5.17)
x i − x j ≥
1
2
(w i + w j ) − w F (1 − Z ij + X ij + Y ij ), 1 ≤ i < j ≤ n + e
(5.18)
x j − x i ≥
1
2
(w i + w j ) − w F (2 − Z ij − X ij + Y ij ), 1 ≤ i < j ≤ n + e
(5.19)
y i − y j ≥
1
2
(h i + h j ) − h F (2 − Z ij + X ij − Y ij ), 1 ≤ i < j ≤ n + e
(5.20)
y j − y i ≥
1
2
(h i + h j ) − h F (3 − Z ij − X ij − Y ij ), 1 ≤ i < j ≤ n + e
(5.21)
z ik = 1, n+ 1 ≤ i ≤ n + e, 1 ≤ k ≤ p
(5.22)
Z ij = 1, n+ 1 ≤ i < j ≤ n + e
(5.23)
X ij , Y ij , Z ij , z ik ∈ {0, 1}, 1 ≤ i < j ≤ n + e, 1 ≤ k ≤ p
(5.24)
h i , w i ≥ 0, 1 ≤ i ≤ n.
(5.25)
Note that as stated above, this formulation is not a MISOCO problem because
of constraints (5.11), (5.12), (5.13), and (5.16). However, the first three of these can
be linearized as explained in Sect. 2.3.1, and the fourth set is equivalent to the SOC
constraints (4.11). After these adjustments, the result is a MISOCO formulation of
MF-FLP.
Constraints (5.7) allocate each department to exactly one floor. Constraints (5.8),
(5.9), and (5.10) set Z ij = 1 if i and j are on the same floor, and 0 otherwise.
Constraints (5.11) compute the vertical distance between each pair of departments.
Note that
p
k=1
k(z ik − z jk )
is equal to the number of floors separating departments i and j .
Constraints (5.12) and (5.13) compute the horizontal distance between each pair
of departments. If departments i and j are on different floors, then the distance
79
1 ≤ i < j ≤ n, n + 1 ≤ ≤ n + e
x i +
1
2
w i ≤
1
2
w F , x i −
1
2
w i ≥ −
1
2
w F , 1 ≤ i ≤ n + e
(5.14)
y i +
1
2
h i ≤
1
2
h F , y i −
1
2
h i ≥ −
1
2
h F , 1 ≤ i ≤ n + e
(5.15)
w i h i ≥ A i , 1 ≤ i ≤ n
(5.16)
w i − βh i ≤ 0, h i − βw i ≤ 0, 1 ≤ i ≤ n
(5.17)
x i − x j ≥
1
2
(w i + w j ) − w F (1 − Z ij + X ij + Y ij ), 1 ≤ i < j ≤ n + e
(5.18)
x j − x i ≥
1
2
(w i + w j ) − w F (2 − Z ij − X ij + Y ij ), 1 ≤ i < j ≤ n + e
(5.19)
y i − y j ≥
1
2
(h i + h j ) − h F (2 − Z ij + X ij − Y ij ), 1 ≤ i < j ≤ n + e
(5.20)
y j − y i ≥
1
2
(h i + h j ) − h F (3 − Z ij − X ij − Y ij ), 1 ≤ i < j ≤ n + e
(5.21)
z ik = 1, n+ 1 ≤ i ≤ n + e, 1 ≤ k ≤ p
(5.22)
Z ij = 1, n+ 1 ≤ i < j ≤ n + e
(5.23)
X ij , Y ij , Z ij , z ik ∈ {0, 1}, 1 ≤ i < j ≤ n + e, 1 ≤ k ≤ p
(5.24)
h i , w i ≥ 0, 1 ≤ i ≤ n.
(5.25)
Note that as stated above, this formulation is not a MISOCO problem because
of constraints (5.11), (5.12), (5.13), and (5.16). However, the first three of these can
be linearized as explained in Sect. 2.3.1, and the fourth set is equivalent to the SOC
constraints (4.11). After these adjustments, the result is a MISOCO formulation of
MF-FLP.
Constraints (5.7) allocate each department to exactly one floor. Constraints (5.8),
(5.9), and (5.10) set Z ij = 1 if i and j are on the same floor, and 0 otherwise.
Constraints (5.11) compute the vertical distance between each pair of departments.
Note that
p
k=1
k(z ik − z jk )
is equal to the number of floors separating departments i and j .
Constraints (5.12) and (5.13) compute the horizontal distance between each pair
of departments. If departments i and j are on different floors, then the distance