3.1 Double-Row Facility Layout
37
We observe that constraints (3.1) and (3.8) are redundant in the presence of
constraints (3.6) and (3.7), but they may be helpful in improving the performance of
a branching algorithm.
3.1.2 Improved Mixed-Integer Linear Optimization Model
with Betweenness Variables
We can improve formulation (3.6)–(3.10) by making use of betweenness information. Specifically, we can change the right-hand side of constraints (3.8) from 0 to a
positive number based on betweenness and thus improve the lower bound obtained
when solving the LO relaxations via a branching algorithm. To achieve this, we
extend the definition of betweenness variables, originally given in Sect. 2.4. For
three distinct departments i, j , and k, define the betweenness variables β ij k as
β ij k =
⎧
⎨
⎩
1, if department k lies between departments i and j
and i, j , and k are all in the same row;
0, otherwise.
Starting from the formulation derived in Sect. 3.1.1 and using these new betweenness variables, we obtain the following improved formulation of the DRFLP:
minimize
n−1
i=1
n
j =i+1
c ij d ij
(3.11)
s.t. d ij ≥ x i − x j , d ij ≥ x j − x i , 1 ≤ i < j ≤ n,
(3.12)
x i +
i + j
2
≤ x j + L(1 − α ij ), 1 ≤ i = j ≤ n,
(3.13)
d ij −
i + j
2
α ij −
i + j
2
α ji ≥
k =i,j
k β kij , 1 ≤ i < j ≤ n
(3.14)
(3.1) − (3.4),
(3.15)
β ij k ≥ α ik + α kj − 1, 1 ≤ i < j ≤ n, k = i, j,
(3.16)
β ij k ≥ α ki + α jk − 1, 1 ≤ i < j ≤ n, k = i, j,
(3.17)
β ij k ≤ α ij + α ji , 1 ≤ i < j ≤ n, k = i, j,
(3.18)
β ij k ≤ α ik + α ki , 1 ≤ i < j ≤ n, k = i, j,
(3.19)