22
2 Layout on a Single Row
We start by defining a set of binary variables γ ij that will perform exactly the
same role as the α ij variables defined in Sect. 2.3.2, but with the two possible values
being {−1, 1} instead of {0, 1}. While the whole SDO approach can be applied using
{0, 1}, we make this change because in SDO it is much more convenient to use the
values {−1, 1} than the usual choice of {0, 1} in LO. We define γ ij as follows:
γ ij =
1 if department i is to the left of department j ,
−1 if department i is to the right of department j .
We immediately observe that γ ij = −γ ji , so we can easily avoid duplication of
variables by requiring that i < j, and changing the sign as well as the order of the
indices whenever i > j occurs.
It is important to point out that in the SDO context, we can use both linear and
quadratic constraints, and indeed it is best to use quadratic expressions as much as
possible to take full advantage of the power of SDO. This means that our approach
to modelling problems using SDO is often quite different to the LO approach. In this
spirit, we choose to express the binary nature of the γ variables using the quadratic
constraints
γ
2
ij = 1 for all i < j.
Let us now develop the constraints necessary to ensure the consistency of the
values assigned to γ ij , following the reasoning applied in Sect. 2.5 for α ij .
First, we note that γ ij = −γ ji corresponds precisely to the relationship α ij =
1 − α ji in the {0, 1} formulations, and hence for the γ variables it is automatically
true that we cannot simultaneously have i to the left of j and j to the left of i.
Second, for any three distinct departments i, j, k, we want to ensure that the
transitivity condition holds:
if i is to the left of j and j is to the left of k, then i is to the left of k.
Observe that this condition is equivalent to
if γ ij = γ jk then γ ik = γ ij .
(2.55)
It can be formulated using the following quadratic constraint:
(γ ij + γ jk )(γ ij − γ ik ) = 0.
(2.56)
The reasoning here is that this constraint requires one of the two expressions in
parentheses to be equal to zero. If the first expression is zero, then γ ij = γ jk , and
there is nothing more to do. If the first expression is not zero, then γ ij = γ jk and the
second expression must be zero, which means that γ ik = γ ij must hold, precisely as
desired. Expanding the expression in (2.56), we can write the constraint in the form
γ ij γ jk − γ ij γ ik − γ ik γ jk = −1, 1 ≤ i < j < k ≤ n,
(2.57)
2 Layout on a Single Row
We start by defining a set of binary variables γ ij that will perform exactly the
same role as the α ij variables defined in Sect. 2.3.2, but with the two possible values
being {−1, 1} instead of {0, 1}. While the whole SDO approach can be applied using
{0, 1}, we make this change because in SDO it is much more convenient to use the
values {−1, 1} than the usual choice of {0, 1} in LO. We define γ ij as follows:
γ ij =
1 if department i is to the left of department j ,
−1 if department i is to the right of department j .
We immediately observe that γ ij = −γ ji , so we can easily avoid duplication of
variables by requiring that i < j, and changing the sign as well as the order of the
indices whenever i > j occurs.
It is important to point out that in the SDO context, we can use both linear and
quadratic constraints, and indeed it is best to use quadratic expressions as much as
possible to take full advantage of the power of SDO. This means that our approach
to modelling problems using SDO is often quite different to the LO approach. In this
spirit, we choose to express the binary nature of the γ variables using the quadratic
constraints
γ
2
ij = 1 for all i < j.
Let us now develop the constraints necessary to ensure the consistency of the
values assigned to γ ij , following the reasoning applied in Sect. 2.5 for α ij .
First, we note that γ ij = −γ ji corresponds precisely to the relationship α ij =
1 − α ji in the {0, 1} formulations, and hence for the γ variables it is automatically
true that we cannot simultaneously have i to the left of j and j to the left of i.
Second, for any three distinct departments i, j, k, we want to ensure that the
transitivity condition holds:
if i is to the left of j and j is to the left of k, then i is to the left of k.
Observe that this condition is equivalent to
if γ ij = γ jk then γ ik = γ ij .
(2.55)
It can be formulated using the following quadratic constraint:
(γ ij + γ jk )(γ ij − γ ik ) = 0.
(2.56)
The reasoning here is that this constraint requires one of the two expressions in
parentheses to be equal to zero. If the first expression is zero, then γ ij = γ jk , and
there is nothing more to do. If the first expression is not zero, then γ ij = γ jk and the
second expression must be zero, which means that γ ik = γ ij must hold, precisely as
desired. Expanding the expression in (2.56), we can write the constraint in the form
γ ij γ jk − γ ij γ ik − γ ik γ jk = −1, 1 ≤ i < j < k ≤ n,
(2.57)