86
5 Extensions and Related Problems
1
2
(h t
i − h F ) ≤ y t
i ≤
1
2
(h F − h t
i ), 1 ≤ i ≤ n, 1 ≤ t ≤ T ,
(5.55)
x t
i +
1
2
w t
i ≤ x t
j −
1
2
w t
j + w F (1 − α t
ij ), 1 ≤ i = j ≤ n, 1 ≤ t ≤ T ,
(5.56)
y t
i +
1
2
h t
i ≤ y t
j −
1
2
h t
j + h F (1 − β t
ij ), 1 ≤ i = j ≤ n, 1 ≤ t ≤ T ,
(5.57)
α t
ij + α t
ji + β t
ij + β t
ji = 1, 1 ≤ i < j ≤ n, 1 ≤ t ≤ T ,
(5.58)
x t
i − x
(t −1)
i
≤ w F r t
i , −x t
i + x
(t −1)
i
≤ w F r t
i , 1 ≤ i ≤ n, 2 ≤ t ≤ T ,
(5.59)
y t
i − y
(t −1)
i
≤ h F r t
i , −y t
i + y
(t −1)
i
≤ h F r t
i , 1 ≤ i ≤ n, 2 ≤ t ≤ T ,
(5.60)
w t
i − w
(t −1)
i
≤ w F r t
i , −w t
i + w
(t −1)
i
≤ w F r t
i , 1 ≤ i ≤ n, 2 ≤ t ≤ T ,
(5.61)
h t
i − h
(t −1)
i
≤ h F r t
i , −h t
i + h
(t −1)
i
≤ h F r t
i , 1 ≤ i ≤ n, 2 ≤ t ≤ T ,
(5.62)
α t
ij , β t
ij , r t
i ∈ {0, 1}, 1 ≤ i, j ≤ n, 1 ≤ t ≤ T .
(5.63)
For each period, almost all the constraints have the same interpretation as for the
UA-FLP in Sect. 4.2. We recall that the constraints (5.52) can be expressed using a
SOC of the form (4.11). The additional constraints specific to the dynamic version
are (5.59)–(5.62). They work in combination with the variables r
t
i to control if there
is some position or shape change for department i from one period to the next.
If r
t
i = 1, then the cost of changing department i at the beginning of period t is
included in the objective function; the coordinates of the centre of i in period t can
be different from those in period t − 1; and the shape of i can change as well. If
r
t
i = 0, then these quantities must remain unchanged from period t − 1 to period t.
5.5 References and Further Reading
The QAP as defined in (5.1) is known as the Koopmans–Beckmann QAP. The first
statement of the QAP in the literature is found in Koopmans and Beckmann (1957),
where the formulation (5.2)–(5.5) was also proposed. Çela (2013) is an excellent
reference on the many aspects of the QAP, which remains a particularly challenging
problem in discrete optimization.
Constraints (5.8)–(5.10) and (5.18)–(5.21) were taken from Patsiatzis and Papageorgiou (2002). Meller and Bozer (1997) present a QAP model to assign depart-
5 Extensions and Related Problems
1
2
(h t
i − h F ) ≤ y t
i ≤
1
2
(h F − h t
i ), 1 ≤ i ≤ n, 1 ≤ t ≤ T ,
(5.55)
x t
i +
1
2
w t
i ≤ x t
j −
1
2
w t
j + w F (1 − α t
ij ), 1 ≤ i = j ≤ n, 1 ≤ t ≤ T ,
(5.56)
y t
i +
1
2
h t
i ≤ y t
j −
1
2
h t
j + h F (1 − β t
ij ), 1 ≤ i = j ≤ n, 1 ≤ t ≤ T ,
(5.57)
α t
ij + α t
ji + β t
ij + β t
ji = 1, 1 ≤ i < j ≤ n, 1 ≤ t ≤ T ,
(5.58)
x t
i − x
(t −1)
i
≤ w F r t
i , −x t
i + x
(t −1)
i
≤ w F r t
i , 1 ≤ i ≤ n, 2 ≤ t ≤ T ,
(5.59)
y t
i − y
(t −1)
i
≤ h F r t
i , −y t
i + y
(t −1)
i
≤ h F r t
i , 1 ≤ i ≤ n, 2 ≤ t ≤ T ,
(5.60)
w t
i − w
(t −1)
i
≤ w F r t
i , −w t
i + w
(t −1)
i
≤ w F r t
i , 1 ≤ i ≤ n, 2 ≤ t ≤ T ,
(5.61)
h t
i − h
(t −1)
i
≤ h F r t
i , −h t
i + h
(t −1)
i
≤ h F r t
i , 1 ≤ i ≤ n, 2 ≤ t ≤ T ,
(5.62)
α t
ij , β t
ij , r t
i ∈ {0, 1}, 1 ≤ i, j ≤ n, 1 ≤ t ≤ T .
(5.63)
For each period, almost all the constraints have the same interpretation as for the
UA-FLP in Sect. 4.2. We recall that the constraints (5.52) can be expressed using a
SOC of the form (4.11). The additional constraints specific to the dynamic version
are (5.59)–(5.62). They work in combination with the variables r
t
i to control if there
is some position or shape change for department i from one period to the next.
If r
t
i = 1, then the cost of changing department i at the beginning of period t is
included in the objective function; the coordinates of the centre of i in period t can
be different from those in period t − 1; and the shape of i can change as well. If
r
t
i = 0, then these quantities must remain unchanged from period t − 1 to period t.
5.5 References and Further Reading
The QAP as defined in (5.1) is known as the Koopmans–Beckmann QAP. The first
statement of the QAP in the literature is found in Koopmans and Beckmann (1957),
where the formulation (5.2)–(5.5) was also proposed. Çela (2013) is an excellent
reference on the many aspects of the QAP, which remains a particularly challenging
problem in discrete optimization.
Constraints (5.8)–(5.10) and (5.18)–(5.21) were taken from Patsiatzis and Papageorgiou (2002). Meller and Bozer (1997) present a QAP model to assign depart-