10
2 Layout on a Single Row
the non-negativity of the coefficients c ij to linearize the constraints d ij = |x i −
x j |. Observe that because c ij ≥ 0, we can relax d ij = |x i − x j | to d ij ≥ |x i −
x j |. This is because no optimal solution has d ij > |x i − x j | since it gives an
unnecessary increase in the value of the objective function. We can then use the
following well-known linearization technique:
d ij ≥ |x i − x j | ⇔ d ij ≥ x i − x j and d ij ≥ x j − x i .
(2.10)
The idea is that because c ij ≥ 0, by the reasoning above, the optimization will
ensure that one of the two linear inequalities on the right-hand side of (2.10) is
tight, i.e., holds with equality, at optimality. Unless x i = x j , only the inequality
corresponding to the larger of the two values x i − x j and x j − x i will be tight,
and this larger value is by definition the value of |x i − x j |.
• The second approach introduces new variables v
+
ij and v
−
ij and defines v
+
ij +
v
−
ij = |x i − x j | for i, j = 1, . . . , n, i < j. Then the objective function is
linearized as
min
x 1 ,...,x n
n−1
i=1
n
j =i+1
c ij (v
+
ij + v
−
ij ),
and the following constraints are added to the formulation:
v
+
ij ≥ 0, v
−
ij ≥ 0, and x i − x j + v
+
ij − v
−
ij = 0.
The idea is that if x i − x j is negative, then v
+
ij = − (x i − x j ) and v
−
ij = 0.
Otherwise, v
+
ij = 0 and v
−
ij = (x i −x j ). Since c ij ≥ 0 and we are minimizing,
any other choices of u ij , v ij will increase the objective function and thus cannot
be optimal.
2.3.2 Linearization of the Nonoverlap Constraints
We also need to linearize the nonoverlap constraints (2.8), which contain the term
|x i − x j |. Here we cannot exploit the fact that c ij ≥ 0 in the objective function.
Instead we introduce binary variables α ij for i, j = 1, . . . , n, i < j to let the
optimization determine the relative position of each pair of departments i and j . In
our single-row problem, either i is to the left of j or vice versa. We encode these
two possibilities using α ij as follows:
α ij =
1 if department i is to the left of department j ,
0 if department j is to the left of department i.
2 Layout on a Single Row
the non-negativity of the coefficients c ij to linearize the constraints d ij = |x i −
x j |. Observe that because c ij ≥ 0, we can relax d ij = |x i − x j | to d ij ≥ |x i −
x j |. This is because no optimal solution has d ij > |x i − x j | since it gives an
unnecessary increase in the value of the objective function. We can then use the
following well-known linearization technique:
d ij ≥ |x i − x j | ⇔ d ij ≥ x i − x j and d ij ≥ x j − x i .
(2.10)
The idea is that because c ij ≥ 0, by the reasoning above, the optimization will
ensure that one of the two linear inequalities on the right-hand side of (2.10) is
tight, i.e., holds with equality, at optimality. Unless x i = x j , only the inequality
corresponding to the larger of the two values x i − x j and x j − x i will be tight,
and this larger value is by definition the value of |x i − x j |.
• The second approach introduces new variables v
+
ij and v
−
ij and defines v
+
ij +
v
−
ij = |x i − x j | for i, j = 1, . . . , n, i < j. Then the objective function is
linearized as
min
x 1 ,...,x n
n−1
i=1
n
j =i+1
c ij (v
+
ij + v
−
ij ),
and the following constraints are added to the formulation:
v
+
ij ≥ 0, v
−
ij ≥ 0, and x i − x j + v
+
ij − v
−
ij = 0.
The idea is that if x i − x j is negative, then v
+
ij = − (x i − x j ) and v
−
ij = 0.
Otherwise, v
+
ij = 0 and v
−
ij = (x i −x j ). Since c ij ≥ 0 and we are minimizing,
any other choices of u ij , v ij will increase the objective function and thus cannot
be optimal.
2.3.2 Linearization of the Nonoverlap Constraints
We also need to linearize the nonoverlap constraints (2.8), which contain the term
|x i − x j |. Here we cannot exploit the fact that c ij ≥ 0 in the objective function.
Instead we introduce binary variables α ij for i, j = 1, . . . , n, i < j to let the
optimization determine the relative position of each pair of departments i and j . In
our single-row problem, either i is to the left of j or vice versa. We encode these
two possibilities using α ij as follows:
α ij =
1 if department i is to the left of department j ,
0 if department j is to the left of department i.