14
2 Layout on a Single Row
It follows that we can express the objective function of the SRFLP as
i
⎛
⎝ 1
2
i + j
+
k =i,j
k β ij k
⎞
⎠ .
We now need some constraints to ensure that the values assigned to the variables
β ij k are consistent. First, for any three distinct departments i, j, k, only one of them
is between the other two, and therefore,
β ij k + β ikj + β jki = 1, 1 ≤ i < j < k ≤ n.
(2.20)
Second, suppose that β ikd = 1, i.e., department d is between departments i and k.
This implies that for every other department j , either d is between i and j or d is
between j and k. This observation leads to the constraints:
β ij d + β jkd − β ikd ≥ 0, for all {i, j, k} ⊆ {1, . . . , n}, d = i, j, k.
(2.21)
Third, by similar reasoning, if d is between i and k, then d cannot simultaneously
be between i and j and between j and k. This can be expressed as
β ij d + β jkd + β ikd ≤ 2, 1 ≤ i < j < k ≤ n, d = i, j, k.
(2.22)
Finally, note that the number of betweenness variables can be reduced by half using
the observation that
β ij d = β jid , 1 ≤ i < j ≤ n, d = i, j.
If we apply this reduction in the number of variables, constraints (2.20) and (2.22)
are unchanged, but constraint (2.21) must be rewritten as three sets of inequalities:
β ij d + β jkd − β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k,
(2.23)
β ij d − β jkd + β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k,
(2.24)
−β ij d + β jkd + β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k.
(2.25)
In this way, we have assembled all the ingredients for a betweenness-based
formulation of the SRFLP:
minimize
i
⎛
⎝
1
2
i + j
+
k =i,j
k β ij k
⎞
⎠
(2.26)
s.t. β ij k + β ikj + β jki = 1, 1 ≤ i < j < k ≤ n,
(2.27)
β ij d + β jkd − β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k,
(2.28)
2 Layout on a Single Row
It follows that we can express the objective function of the SRFLP as
i
⎛
⎝ 1
2
i + j
+
k =i,j
k β ij k
⎞
⎠ .
We now need some constraints to ensure that the values assigned to the variables
β ij k are consistent. First, for any three distinct departments i, j, k, only one of them
is between the other two, and therefore,
β ij k + β ikj + β jki = 1, 1 ≤ i < j < k ≤ n.
(2.20)
Second, suppose that β ikd = 1, i.e., department d is between departments i and k.
This implies that for every other department j , either d is between i and j or d is
between j and k. This observation leads to the constraints:
β ij d + β jkd − β ikd ≥ 0, for all {i, j, k} ⊆ {1, . . . , n}, d = i, j, k.
(2.21)
Third, by similar reasoning, if d is between i and k, then d cannot simultaneously
be between i and j and between j and k. This can be expressed as
β ij d + β jkd + β ikd ≤ 2, 1 ≤ i < j < k ≤ n, d = i, j, k.
(2.22)
Finally, note that the number of betweenness variables can be reduced by half using
the observation that
β ij d = β jid , 1 ≤ i < j ≤ n, d = i, j.
If we apply this reduction in the number of variables, constraints (2.20) and (2.22)
are unchanged, but constraint (2.21) must be rewritten as three sets of inequalities:
β ij d + β jkd − β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k,
(2.23)
β ij d − β jkd + β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k,
(2.24)
−β ij d + β jkd + β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k.
(2.25)
In this way, we have assembled all the ingredients for a betweenness-based
formulation of the SRFLP:
minimize
i
⎛
⎝
1
2
i + j
+
k =i,j
k β ij k
⎞
⎠
(2.26)
s.t. β ij k + β ikj + β jki = 1, 1 ≤ i < j < k ≤ n,
(2.27)
β ij d + β jkd − β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k,
(2.28)