20
2 Layout on a Single Row
Y ij ik ≥ −1 + α ij + α ik ,
Y ij ik ≤ α ij , Y ij ik ≤ α ik , 1 ≤ i, j, k ≤ n,
(2.46)
Y ikj k ≥ −1 + α jk + α ik , Y ikj k ≤ α ik , Y ikj k ≤ α jk , 1 ≤ i, j, k ≤ n,
(2.47)
α ij + α ji = 1, 1 ≤ i < j ≤ n,
(2.48)
α ij + α jk + α ki ≤ 2, 1 ≤ i = j = k ≤ n,
(2.49)
Y ij kd = Y kdij , 1 ≤ i = j, k = d ≤ n,
(2.50)
α ij ∈ {0, 1}, 1 ≤ i = j ≤ n.
(2.51)
As we observed for the binary quadratic formulation, the number of α variables
can be reduced by substituting half of them using (2.48). The same is true for the
Y variables, based on constraint (2.50). This reduction is useful for computational
efficiency, and it should be carried out before the model is handed over to the solver.
2.6.2 Improving the Linearized Formulation
As already noted, valid inequalities are essential for the efficient solution of
mathematical optimization models. The linearized formulation (2.44)–(2.51) can
be improved by the addition of valid inequalities.
Valid inequalities for the SRFLP and other problems can often be generated
using a framework known as the reformulation–linearization technique (RLT).
The simple but extremely powerful process behind RLT can be summarized in two
steps:
1. The reformulation step introduces new terms involving the product of two (or
more) variables by multiplying one or more of the constraints by one or more of
the variables.
2. The linearization step replaces each new product term by a new variable and links
the new variables to the former variables using linear constraints.
We illustrate here a straightforward application of RLT but emphasize that the
framework is highly flexible and can be used in different ways.
Before applying RLT, we revisit constraints (2.49) and observe that for each
choice of distinct i, j, k, two different 3-cycles are forbidden, namely i → j →
k → i and i → k → j → i. Therefore, we can split each of the constraints into
two inequalities:
α ij + α jk + α ki ≤ 2 and α ik + α kj + α ji ≤ 2, 1 ≤ i = j = k ≤ n.
2 Layout on a Single Row
Y ij ik ≥ −1 + α ij + α ik ,
Y ij ik ≤ α ij , Y ij ik ≤ α ik , 1 ≤ i, j, k ≤ n,
(2.46)
Y ikj k ≥ −1 + α jk + α ik , Y ikj k ≤ α ik , Y ikj k ≤ α jk , 1 ≤ i, j, k ≤ n,
(2.47)
α ij + α ji = 1, 1 ≤ i < j ≤ n,
(2.48)
α ij + α jk + α ki ≤ 2, 1 ≤ i = j = k ≤ n,
(2.49)
Y ij kd = Y kdij , 1 ≤ i = j, k = d ≤ n,
(2.50)
α ij ∈ {0, 1}, 1 ≤ i = j ≤ n.
(2.51)
As we observed for the binary quadratic formulation, the number of α variables
can be reduced by substituting half of them using (2.48). The same is true for the
Y variables, based on constraint (2.50). This reduction is useful for computational
efficiency, and it should be carried out before the model is handed over to the solver.
2.6.2 Improving the Linearized Formulation
As already noted, valid inequalities are essential for the efficient solution of
mathematical optimization models. The linearized formulation (2.44)–(2.51) can
be improved by the addition of valid inequalities.
Valid inequalities for the SRFLP and other problems can often be generated
using a framework known as the reformulation–linearization technique (RLT).
The simple but extremely powerful process behind RLT can be summarized in two
steps:
1. The reformulation step introduces new terms involving the product of two (or
more) variables by multiplying one or more of the constraints by one or more of
the variables.
2. The linearization step replaces each new product term by a new variable and links
the new variables to the former variables using linear constraints.
We illustrate here a straightforward application of RLT but emphasize that the
framework is highly flexible and can be used in different ways.
Before applying RLT, we revisit constraints (2.49) and observe that for each
choice of distinct i, j, k, two different 3-cycles are forbidden, namely i → j →
k → i and i → k → j → i. Therefore, we can split each of the constraints into
two inequalities:
α ij + α jk + α ki ≤ 2 and α ik + α kj + α ji ≤ 2, 1 ≤ i = j = k ≤ n.