24
2 Layout on a Single Row
It remains to determine how to handle the requirement that the matrix Γ be of
the form (2.61). We make the following observations:
• First, observe that Γ is by construction a rank-one matrix. This is because every
column of Γ is a multiple of the vector g; in fact, each column is equal to either
g or −g. We denote this by rank (Γ ) = 1.
• Second, observe that because each γ ij is equal to −1 or 1, all the entries of Γ
are also equal to −1 or 1. It follows that the diagonal entries of Γ are equal to
1 (because they are of the form γ 2
ij ). We denote this by diag (Γ ) = e, where e
denotes the vector of all ones (of the appropriate dimension in the context).
• Third, by Theorem A.2 in Appendix A, we have that Γ is positive semidefinite
(PSD). We denote this by Γ 0.
It turns out that these three conditions suffice to ensure that Γ has the form (2.61).
Therefore, we can formulate the SRFLP as follows:
minimize
⎛
⎝
i
2
⎞
⎠
n
k=1
k
−
i
2
⎡
⎣
k
i
k>j
k Γ ik,j k
⎤
⎦
(2.62)
s.t. Γ ij,j k − Γ ij,ik − Γ ik,j k = −1, 1 ≤ i < j < k ≤ n,
(2.63)
rank (Γ ) = 1,
(2.64)
diag (Γ ) = e,
(2.65)
Γ 0.
(2.66)
This formulation is nearly an SDO problem. The only constraint that cannot be
handled by SDO solvers is (2.64) because it restricts the rank of the matrix variables.
This constraint can be interpreted as an “integrality” constraint, in the sense that
among all the matrices that are PSD and have all diagonal entries equal to 1, those
whose entries are all integer (equal to −1 or 1), are precisely those that have rank
equal to 1. It is therefore natural to relax this constraint (analogously to relaxations
in MILO) by replacing it with bounds on the entries of Γ :
−1 ≤ Γ p,q ≤ 1.
Conveniently, it turns out that these bounds are implied by the combination of the
constraints diag (Γ ) = e and Γ 0. Indeed, by (A.2) in Appendix A, we have that
Γ 2
p,q ≤ 1 for all pairs p, q. Hence, relaxing the rank constraint in the formulation
above comes down to simply removing it.
2 Layout on a Single Row
It remains to determine how to handle the requirement that the matrix Γ be of
the form (2.61). We make the following observations:
• First, observe that Γ is by construction a rank-one matrix. This is because every
column of Γ is a multiple of the vector g; in fact, each column is equal to either
g or −g. We denote this by rank (Γ ) = 1.
• Second, observe that because each γ ij is equal to −1 or 1, all the entries of Γ
are also equal to −1 or 1. It follows that the diagonal entries of Γ are equal to
1 (because they are of the form γ 2
ij ). We denote this by diag (Γ ) = e, where e
denotes the vector of all ones (of the appropriate dimension in the context).
• Third, by Theorem A.2 in Appendix A, we have that Γ is positive semidefinite
(PSD). We denote this by Γ 0.
It turns out that these three conditions suffice to ensure that Γ has the form (2.61).
Therefore, we can formulate the SRFLP as follows:
minimize
⎛
⎝
i
2
⎞
⎠
n
k=1
k
−
i
2
⎡
⎣
k
i
k>j
k Γ ik,j k
⎤
⎦
(2.62)
s.t. Γ ij,j k − Γ ij,ik − Γ ik,j k = −1, 1 ≤ i < j < k ≤ n,
(2.63)
rank (Γ ) = 1,
(2.64)
diag (Γ ) = e,
(2.65)
Γ 0.
(2.66)
This formulation is nearly an SDO problem. The only constraint that cannot be
handled by SDO solvers is (2.64) because it restricts the rank of the matrix variables.
This constraint can be interpreted as an “integrality” constraint, in the sense that
among all the matrices that are PSD and have all diagonal entries equal to 1, those
whose entries are all integer (equal to −1 or 1), are precisely those that have rank
equal to 1. It is therefore natural to relax this constraint (analogously to relaxations
in MILO) by replacing it with bounds on the entries of Γ :
−1 ≤ Γ p,q ≤ 1.
Conveniently, it turns out that these bounds are implied by the combination of the
constraints diag (Γ ) = e and Γ 0. Indeed, by (A.2) in Appendix A, we have that
Γ 2
p,q ≤ 1 for all pairs p, q. Hence, relaxing the rank constraint in the formulation
above comes down to simply removing it.