4.3 Sequence-Pair Formulation
63
Fig. 4.3 Layout
corresponding to the
sequence-pair
Γ + = {415263} and
Γ − = {124536}
5
6
1
2
3
4
5
6
Figure 4.3 shows an example of a layout of six departments for which a sequencepair is
Γ + = {415263}, Γ − = {124536}.
We now explain how the sequence-pair structure can be incorporated into a
MISOCO model. Given a sequence-pair (Γ + , Γ − ), we define the following binary
variables for all 1 ≤ i ≤ n and 1 ≤ j ≤ n:
α ij =
1 if i precedes j in Γ + ,
0 otherwise,
β ij =
1 if i precedes j in Γ − ,
0 otherwise.
The following proposition is straightforward to check and is illustrated in
Fig. 4.4.
Proposition 4.1 For any two departments i and j , the following hold:
• if α ij = 1 and β ij = 1, then i is to the left of j ;
• if α ij = 0 and β ij = 0, then i is to the right of j ;
• if α ij = 0 and β ij = 1, then i is below j ;
• if α ij = 1 and β ij = 0, then i is above j .
For example, consider the layout and sequence-pair in Fig. 4.3. Department 4
precedes department 5 in both Γ + and Γ − , hence (α 4,5 , β 4,5 ) = (1, 1), which
correctly reflects the relationship between 4 and 5 according to Fig. 4.4, i.e.,
department 5 is to the right of department 4. By contrast, department 4 precedes
department 2 only in Γ + , so (α 4,2 , β 4,2 ) = (1, 0), i.e., department 2 is below
department 4 as per Fig. 4.4.