40
3 Layout on Several Rows
z kij + z kj i ≤ y ik , 1 ≤ i < j ≤ n, k = 1, . . . , m,
(3.32)
z kij + z kj i ≤ y jk , 1 ≤ i < j ≤ n, k = 1, . . . , m,
(3.33)
z kij + z kj i + 1 ≥ y ik + y jk , 1 ≤ i < j ≤ n, k = 1, . . . , m,
(3.34)
x ik ≥ 0, i = 1, . . . , n, k = 1, . . . , m,
v
+
ij , v
−
ij ≥ 0, 1 ≤ i < j ≤ n,
y ik ∈ {0, 1}, i = 1, . . . , n, k = 1, . . . , m,
z kij ∈ {0, 1}, 1 ≤ i = j ≤ n, k = 1, . . . , m.
(3.35)
Constraints (3.27) compute the distances between departments using the second
linearization approach described in Sect. 2.3.1. Constraints (3.28) set x ik = 0 when
department i is not assigned to row k. Constraints (3.29) ensure that a department
is assigned to just one row. Constraints (3.30) and (3.31) prevent departments from
overlapping if they are located in the same row. Constraints (3.32)–(3.34) ensure
consistency between the variables y and z as follows: if y ik = 1 and y jk = 1, then
(3.32)–(3.34) ensure that exactly one of z kij and z kj i is equal to one. Otherwise, at
least one of y ik or y jk is equal to zero, and one of (3.32) and (3.33) sets both z kij
and z kj i to zero.
We point out that this model is designed for an arbitrary number of rows m, and
therefore it can be applied to double-row layout (m = 2). However, specialized
models for that case are normally more efficient than this general model.
3.2.2 Mixed-Integer Linear Optimization Model
with Continuous Row Assignments
The formulation in this section is a natural extension of the model (3.23)–(3.26): the
variable y i that indicates the row assignment for each department is now continuous.
Like the model presented in the previous subsection and most other mathematical
optimization formulations, this model uses binary variables to prevent overlap.
Unlike most other models, however, it uses continuous variables for the assignment
of departments to rows because it can be proved that these variables will always
attain integer values at optimality; the proof is presented in Sect. 3.2.3. This means
that the departments are assigned to rows without the need for rounding or a similar
operation.
For each department i, we use the variable x i to represent its horizontal position
(within the row it is assigned to) and the variable y i to represent its vertical position
(the row it is assigned to). For each pair of departments i and j , we use the following
3 Layout on Several Rows
z kij + z kj i ≤ y ik , 1 ≤ i < j ≤ n, k = 1, . . . , m,
(3.32)
z kij + z kj i ≤ y jk , 1 ≤ i < j ≤ n, k = 1, . . . , m,
(3.33)
z kij + z kj i + 1 ≥ y ik + y jk , 1 ≤ i < j ≤ n, k = 1, . . . , m,
(3.34)
x ik ≥ 0, i = 1, . . . , n, k = 1, . . . , m,
v
+
ij , v
−
ij ≥ 0, 1 ≤ i < j ≤ n,
y ik ∈ {0, 1}, i = 1, . . . , n, k = 1, . . . , m,
z kij ∈ {0, 1}, 1 ≤ i = j ≤ n, k = 1, . . . , m.
(3.35)
Constraints (3.27) compute the distances between departments using the second
linearization approach described in Sect. 2.3.1. Constraints (3.28) set x ik = 0 when
department i is not assigned to row k. Constraints (3.29) ensure that a department
is assigned to just one row. Constraints (3.30) and (3.31) prevent departments from
overlapping if they are located in the same row. Constraints (3.32)–(3.34) ensure
consistency between the variables y and z as follows: if y ik = 1 and y jk = 1, then
(3.32)–(3.34) ensure that exactly one of z kij and z kj i is equal to one. Otherwise, at
least one of y ik or y jk is equal to zero, and one of (3.32) and (3.33) sets both z kij
and z kj i to zero.
We point out that this model is designed for an arbitrary number of rows m, and
therefore it can be applied to double-row layout (m = 2). However, specialized
models for that case are normally more efficient than this general model.
3.2.2 Mixed-Integer Linear Optimization Model
with Continuous Row Assignments
The formulation in this section is a natural extension of the model (3.23)–(3.26): the
variable y i that indicates the row assignment for each department is now continuous.
Like the model presented in the previous subsection and most other mathematical
optimization formulations, this model uses binary variables to prevent overlap.
Unlike most other models, however, it uses continuous variables for the assignment
of departments to rows because it can be proved that these variables will always
attain integer values at optimality; the proof is presented in Sect. 3.2.3. This means
that the departments are assigned to rows without the need for rounding or a similar
operation.
For each department i, we use the variable x i to represent its horizontal position
(within the row it is assigned to) and the variable y i to represent its vertical position
(the row it is assigned to). For each pair of departments i and j , we use the following