26
2 Layout on a Single Row
variables, these inequalities take the following form:
Γ p,q + Γ p,r + Γ q,r ≥ −1
(2.71)
Γ p,q − Γ p,r − Γ q,r ≥ −1
(2.72)
−Γ p,q − Γ p,r + Γ q,r ≥ −1
(2.73)
−Γ p,q + Γ p,r − Γ q,r ≥ −1,
(2.74)
where p, q, r are any three distinct pairs of departments.
For the specific case of the SDO relaxation of SRFLP, we observe that not all of
these inequalities will help to tighten the relaxation. Specifically, suppose that the
pairs p, q, r are equal to ij , ik, and j k for any three departments i, j, k. Then it is
straightforward to check that the inequalities (2.71)–(2.74) are implied by constraint
(2.68). Therefore, the 4
n
3
triangle inequalities arising from the choices of pairs of
the form {p, q, r} = {ij, ik, j k} cannot improve the SDO relaxation. However,
for choices of pairs p, q, r that involve four or more departments, the triangle
inequalities can help significantly.
Another class of valid inequalities that has been useful for tightening the SDO
relaxation of SRFLP is
− 1 − γ st ≤ γ ij + γ jk − γ ik + Γ ij,st + Γ jk,st − Γ ik,st ≤ 1 + γ st ,
(2.75)
− 1 + γ st ≤ γ ij + γ jk − γ ik − Γ ij,st − Γ jk,st + Γ ik,st ≤ 1 − γ st ,
(2.76)
for all 1 ≤ i < j < k ≤ n, 1 ≤ s < t ≤ n. These inequalities were obtained using
the Lovász–Schrijver (LS) procedure, which is analogous to the RLT framework. A
fundamental idea in these frameworks is to exploit the fact that any binary solution
must satisfy the nonlinear equation γ 2
ij = γ ij for all 1 ≤ i < j ≤ n. We do not give
the details here and refer the reader to Sect. 2.10 for further information.
2.8 Inequality Separation
We have presented several classes of inequalities applicable to the SRFLP. We have
also mentioned two procedures to generate such classes for the SRFLP, and indeed
for general optimization problems, namely RLT and LS. The reader may suspect (or
already know) that the number of valid inequalities available is very large. In general
it is not possible or desirable to add every known valid inequality to a relaxation,
whether it is an LO or an SDO problem.
Consider the triangle inequalities (2.71)–(2.74). There are 4
(
n
2 )
3
of them, which
means their number is O(n 6 ). We can omit the 4
n
3
implied inequalities, but we still
have far too many to add them all to the SDO relaxation. Moreover, given a specific
instance of the SRFLP, the vast majority of them will not be active at the optimal
2 Layout on a Single Row
variables, these inequalities take the following form:
Γ p,q + Γ p,r + Γ q,r ≥ −1
(2.71)
Γ p,q − Γ p,r − Γ q,r ≥ −1
(2.72)
−Γ p,q − Γ p,r + Γ q,r ≥ −1
(2.73)
−Γ p,q + Γ p,r − Γ q,r ≥ −1,
(2.74)
where p, q, r are any three distinct pairs of departments.
For the specific case of the SDO relaxation of SRFLP, we observe that not all of
these inequalities will help to tighten the relaxation. Specifically, suppose that the
pairs p, q, r are equal to ij , ik, and j k for any three departments i, j, k. Then it is
straightforward to check that the inequalities (2.71)–(2.74) are implied by constraint
(2.68). Therefore, the 4
n
3
triangle inequalities arising from the choices of pairs of
the form {p, q, r} = {ij, ik, j k} cannot improve the SDO relaxation. However,
for choices of pairs p, q, r that involve four or more departments, the triangle
inequalities can help significantly.
Another class of valid inequalities that has been useful for tightening the SDO
relaxation of SRFLP is
− 1 − γ st ≤ γ ij + γ jk − γ ik + Γ ij,st + Γ jk,st − Γ ik,st ≤ 1 + γ st ,
(2.75)
− 1 + γ st ≤ γ ij + γ jk − γ ik − Γ ij,st − Γ jk,st + Γ ik,st ≤ 1 − γ st ,
(2.76)
for all 1 ≤ i < j < k ≤ n, 1 ≤ s < t ≤ n. These inequalities were obtained using
the Lovász–Schrijver (LS) procedure, which is analogous to the RLT framework. A
fundamental idea in these frameworks is to exploit the fact that any binary solution
must satisfy the nonlinear equation γ 2
ij = γ ij for all 1 ≤ i < j ≤ n. We do not give
the details here and refer the reader to Sect. 2.10 for further information.
2.8 Inequality Separation
We have presented several classes of inequalities applicable to the SRFLP. We have
also mentioned two procedures to generate such classes for the SRFLP, and indeed
for general optimization problems, namely RLT and LS. The reader may suspect (or
already know) that the number of valid inequalities available is very large. In general
it is not possible or desirable to add every known valid inequality to a relaxation,
whether it is an LO or an SDO problem.
Consider the triangle inequalities (2.71)–(2.74). There are 4
(
n
2 )
3
of them, which
means their number is O(n 6 ). We can omit the 4
n
3
implied inequalities, but we still
have far too many to add them all to the SDO relaxation. Moreover, given a specific
instance of the SRFLP, the vast majority of them will not be active at the optimal