12
2 Layout on a Single Row
Specifically, consider the case α ij = 1 with departments i and j placed as far
apart as possible in a row of length L, with L as defined earlier. Suppose (without
loss of generality) that i is to the left of j . Then x i =
1
2 i and x j = L −
1
2 j ,
and therefore,
x i − x j =
1
2
i − (L −
1
2
j ) =
1
2
(( i + j ) − L.
We conclude that in this case, M = L is a valid choice for (2.11). By similar
reasoning, it follows that this value is also valid for (2.12), and for the case α ij = 0.
2.3.4 Mixed-Integer Linear Optimization Formulation
Applying the approaches in Sects. 2.3.1 and 2.3.2 to the formulation (2.7–2.9), we
obtain a first MILO model for single-row layout:
minimize
i
(2.13)
s.t. x i − x j + u ij − v ij = 0, 1 ≤ i < j ≤ n,
(2.14)
x i − x j + Lα ij ≥
1
2
(( i + j ), 1 ≤ i < j ≤ n,
(2.15)
x j − x i + L(1 − α ij ) ≥
1
2
(( i + j ), 1 ≤ i < j ≤ n,
(2.16)
1
2
i ≤ x i ≤ L −
1
2
i , 1 ≤ i ≤ n,
(2.17)
α ij ∈ {0, 1}, i = 1, . . . , n − 1, 1 ≤ i < j ≤ n.
(2.18)
u ij , v ij ≥ 0, 1 ≤ i < j ≤ n.
(2.19)
This is only one of various MILO formulations of the SRFLP. If we can find a
formulation for which the corresponding relaxations are tighter, then branching
methods will perform better and also provide tighter global lower bounds on the
optimal value.
The next section presents a way to formulate the SRFLP without continuous
variables.
2 Layout on a Single Row
Specifically, consider the case α ij = 1 with departments i and j placed as far
apart as possible in a row of length L, with L as defined earlier. Suppose (without
loss of generality) that i is to the left of j . Then x i =
1
2 i and x j = L −
1
2 j ,
and therefore,
x i − x j =
1
2
i − (L −
1
2
j ) =
1
2
(( i + j ) − L.
We conclude that in this case, M = L is a valid choice for (2.11). By similar
reasoning, it follows that this value is also valid for (2.12), and for the case α ij = 0.
2.3.4 Mixed-Integer Linear Optimization Formulation
Applying the approaches in Sects. 2.3.1 and 2.3.2 to the formulation (2.7–2.9), we
obtain a first MILO model for single-row layout:
minimize
i
(2.13)
s.t. x i − x j + u ij − v ij = 0, 1 ≤ i < j ≤ n,
(2.14)
x i − x j + Lα ij ≥
1
2
(( i + j ), 1 ≤ i < j ≤ n,
(2.15)
x j − x i + L(1 − α ij ) ≥
1
2
(( i + j ), 1 ≤ i < j ≤ n,
(2.16)
1
2
i ≤ x i ≤ L −
1
2
i , 1 ≤ i ≤ n,
(2.17)
α ij ∈ {0, 1}, i = 1, . . . , n − 1, 1 ≤ i < j ≤ n.
(2.18)
u ij , v ij ≥ 0, 1 ≤ i < j ≤ n.
(2.19)
This is only one of various MILO formulations of the SRFLP. If we can find a
formulation for which the corresponding relaxations are tighter, then branching
methods will perform better and also provide tighter global lower bounds on the
optimal value.
The next section presents a way to formulate the SRFLP without continuous
variables.