2.7 Semidefinite Optimization Formulation
25
The resulting SDO relaxation of the SRFLP is
minimize
⎛
⎝
i
2
⎞
⎠
n
k=1
k
−
i
2
⎡
⎣
k
i
k>j
k Γ ik,j k
⎤
⎦
(2.67)
s.t. Γ ij,j k − Γ ij,ik − Γ ik,j k = −1, 1 ≤ i < j < k ≤ n,
(2.68)
diag (Γ ) = e,
(2.69)
Γ 0.
(2.70)
Note that unless the optimal solution matrix Γ ∗ has rank equal to 1, we obtain
only a lower bound on the optimal value of the SRFLP, and not a feasible solution.
Therefore, as in MILO, we are interested in ways to tighten the relaxation, and in
general we may need to apply an enumeration algorithm to obtain the global optimal
solution.
We observed earlier that we can reverse the order of the departments in the
SRFLP without changing the value of the objective function. This reversal of the
order is equivalent to replacing every γ ij value by its negative. We observe that
if we do this, then there is no change to the SDO formulation or its relaxation,
because all the expressions involved are quadratic in the γ variables. In this way,
the SDO formulation and the corresponding SDO relaxation implicitly account for
the symmetry of the SRFLP.
2.7.1 Improving the Semidefinite Formulation
The SDO formulation can be improved by the addition of valid inequalities, as was
done for the LO formulation. In particular, the RLT framework can be applied to
generate valid inequalities for the entries of Γ . Because the SDO relaxation is in
practice already very tight, it turns out that a single class of valid inequalities is
highly effective. These inequalities are known as the triangle inequalities, and they
are well known in combinatorial optimization.
For our purposes, we focus on the interpretation that the triangle inequalities
model the fact that for any assignment of the values {−1, 1} to the variables γ ,
the values of the matrix entries Γ p,q , Γ p,r , and Γ q,r , where p, q, r are any three
distinct pairs of departments, must comprise an even number of negative values. In
other words, either none of these three matrix entries equal −1, or precisely two of
them equal −1. (It is straightforward to verify this claim by checking all possible
cases.) This demonstrates the validity of the triangle inequalities. For {−1, 1} binary
25
The resulting SDO relaxation of the SRFLP is
minimize
⎛
⎝
i
2
⎞
⎠
n
k=1
k
−
i
2
⎡
⎣
k
i
k>j
k Γ ik,j k
⎤
⎦
(2.67)
s.t. Γ ij,j k − Γ ij,ik − Γ ik,j k = −1, 1 ≤ i < j < k ≤ n,
(2.68)
diag (Γ ) = e,
(2.69)
Γ 0.
(2.70)
Note that unless the optimal solution matrix Γ ∗ has rank equal to 1, we obtain
only a lower bound on the optimal value of the SRFLP, and not a feasible solution.
Therefore, as in MILO, we are interested in ways to tighten the relaxation, and in
general we may need to apply an enumeration algorithm to obtain the global optimal
solution.
We observed earlier that we can reverse the order of the departments in the
SRFLP without changing the value of the objective function. This reversal of the
order is equivalent to replacing every γ ij value by its negative. We observe that
if we do this, then there is no change to the SDO formulation or its relaxation,
because all the expressions involved are quadratic in the γ variables. In this way,
the SDO formulation and the corresponding SDO relaxation implicitly account for
the symmetry of the SRFLP.
2.7.1 Improving the Semidefinite Formulation
The SDO formulation can be improved by the addition of valid inequalities, as was
done for the LO formulation. In particular, the RLT framework can be applied to
generate valid inequalities for the entries of Γ . Because the SDO relaxation is in
practice already very tight, it turns out that a single class of valid inequalities is
highly effective. These inequalities are known as the triangle inequalities, and they
are well known in combinatorial optimization.
For our purposes, we focus on the interpretation that the triangle inequalities
model the fact that for any assignment of the values {−1, 1} to the variables γ ,
the values of the matrix entries Γ p,q , Γ p,r , and Γ q,r , where p, q, r are any three
distinct pairs of departments, must comprise an even number of negative values. In
other words, either none of these three matrix entries equal −1, or precisely two of
them equal −1. (It is straightforward to verify this claim by checking all possible
cases.) This demonstrates the validity of the triangle inequalities. For {−1, 1} binary