2.4 Betweenness-Based Binary Linear Optimization Formulation
13
2.4 Betweenness-Based Binary Linear Optimization
Formulation
The model that we present in this section is based on the following observation: it
is not necessary to know the position of each department along the row to formulate
the SRFLP. This is because for each pair of departments i and j , it suffices to know
which departments are placed between i and j . In other words, the key concept for
defining a single-row layout is betweenness.
This can be observed if we express the SRFLP in the following form:
min
π∈Π n
i
1
2
i + j
+ D π (i, j )
,
where D π (i, j ) is the total row space that is taken by the departments located
between i and j under permutation π. For example, with the permutation π of
10 departments illustrated in Fig. 2.5, D π (i, j ) = k 8 + k 1 + k 6 . It follows that
D π (i, j ) is precisely the sum of the lengths of the departments between i and j
under π, under the assumption that the departments are placed with no empty space
between them. This assumption will hold if the weights c ij of the objective function
are all greater than or equal to zero, as observed earlier, or if the length of the row
is L =
n
i=1 i .
To obtain a formulation based on betweenness, instead of defining variables that
determine the position of each department or whether a given department is to the
left or right of another, we want variables that indicate that a given department
is between two others, neither of them necessarily located right next to the given
department. We proceed as follows.
For any three distinct departments i, j, k ∈ {1, . . . , n}, define the betweenness
variable β ij k as
β ij k =
1, if department k lies between departments i and j,
0, otherwise.
Using these variables, it is straightforward to deduce that D π (i, j ) =
k =i,j
k β ij k ,
which is the sum of the lengths of all the departments between i and j . Note that
this holds regardless of the relative positions of departments i and j along the row.
k 4
k 7
i
k 8
k 1
k 6
j
k 5
k 2
k 3
Fig. 2.5 Illustration of betweenness: the distance between i and j equals k 8 + k 1 + k 6
13
2.4 Betweenness-Based Binary Linear Optimization
Formulation
The model that we present in this section is based on the following observation: it
is not necessary to know the position of each department along the row to formulate
the SRFLP. This is because for each pair of departments i and j , it suffices to know
which departments are placed between i and j . In other words, the key concept for
defining a single-row layout is betweenness.
This can be observed if we express the SRFLP in the following form:
min
π∈Π n
i
1
2
i + j
+ D π (i, j )
,
where D π (i, j ) is the total row space that is taken by the departments located
between i and j under permutation π. For example, with the permutation π of
10 departments illustrated in Fig. 2.5, D π (i, j ) = k 8 + k 1 + k 6 . It follows that
D π (i, j ) is precisely the sum of the lengths of the departments between i and j
under π, under the assumption that the departments are placed with no empty space
between them. This assumption will hold if the weights c ij of the objective function
are all greater than or equal to zero, as observed earlier, or if the length of the row
is L =
n
i=1 i .
To obtain a formulation based on betweenness, instead of defining variables that
determine the position of each department or whether a given department is to the
left or right of another, we want variables that indicate that a given department
is between two others, neither of them necessarily located right next to the given
department. We proceed as follows.
For any three distinct departments i, j, k ∈ {1, . . . , n}, define the betweenness
variable β ij k as
β ij k =
1, if department k lies between departments i and j,
0, otherwise.
Using these variables, it is straightforward to deduce that D π (i, j ) =
k =i,j
k β ij k ,
which is the sum of the lengths of all the departments between i and j . Note that
this holds regardless of the relative positions of departments i and j along the row.
k 4
k 7
i
k 8
k 1
k 6
j
k 5
k 2
k 3
Fig. 2.5 Illustration of betweenness: the distance between i and j equals k 8 + k 1 + k 6