42
3 Layout on Several Rows
create the rows. Constraints (3.43)–(3.44) ensure that y i = y j when departments i
and j are placed in the same row. Constraints (3.45) provide bounds on the variables
y i , and in particular they restrict every feasible solution to have no more than m rows
(each of width d). Constraints (3.46) provide bounds on the variables x i . Constraints
(3.47) require the separation of i and j in one of the two dimensions (they may
be separated in both dimensions at optimality). Constraints (3.48) and (3.49) are
transitivity constraints, as seen earlier. Finally, constraints (3.50) require the α and
β variables to be binary.
We observe that constraints (3.45) do not guarantee an optimal solution with
exactly m rows but rather at most m rows. Thus, this model for the MRFLP is more
general than that in Sect. 3.2.1 because it decides the optimal number of rows; most
other models require the number of rows to be prespecified.
3.2.3 Proof of the Integrality of Row Assignments at Optimality
As mentioned above, the formulation presented in Sect. 3.2.2 uses continuous
variables y i to represent the vertical position of each department, i.e., the assignment
of departments to rows. It turns out that at optimality, the variables y i always take
on integer values, and hence the row assignments are well defined. The proof of this
fact uses the concept of total unimodularity. We first state the required theoretical
concepts and then give the proof.
Definition 3.1 A matrix A with integer elements is totally unimodular (TU) if the
determinant of each square submatrix of A is equal to 0, 1, or −1.
Example 3.1 The matrix
⎡
⎣
0 1 1 0
−1 0 0 0
0 0 −1 1
⎤
⎦
is TU, but the matrix
⎡
⎣
0 1 1 0
−1 0 0 0
0 1 −1 1
⎤
⎦
is not (because the determinant of the submatrix
1 1
1 −1
equals −2).
3 Layout on Several Rows
create the rows. Constraints (3.43)–(3.44) ensure that y i = y j when departments i
and j are placed in the same row. Constraints (3.45) provide bounds on the variables
y i , and in particular they restrict every feasible solution to have no more than m rows
(each of width d). Constraints (3.46) provide bounds on the variables x i . Constraints
(3.47) require the separation of i and j in one of the two dimensions (they may
be separated in both dimensions at optimality). Constraints (3.48) and (3.49) are
transitivity constraints, as seen earlier. Finally, constraints (3.50) require the α and
β variables to be binary.
We observe that constraints (3.45) do not guarantee an optimal solution with
exactly m rows but rather at most m rows. Thus, this model for the MRFLP is more
general than that in Sect. 3.2.1 because it decides the optimal number of rows; most
other models require the number of rows to be prespecified.
3.2.3 Proof of the Integrality of Row Assignments at Optimality
As mentioned above, the formulation presented in Sect. 3.2.2 uses continuous
variables y i to represent the vertical position of each department, i.e., the assignment
of departments to rows. It turns out that at optimality, the variables y i always take
on integer values, and hence the row assignments are well defined. The proof of this
fact uses the concept of total unimodularity. We first state the required theoretical
concepts and then give the proof.
Definition 3.1 A matrix A with integer elements is totally unimodular (TU) if the
determinant of each square submatrix of A is equal to 0, 1, or −1.
Example 3.1 The matrix
⎡
⎣
0 1 1 0
−1 0 0 0
0 0 −1 1
⎤
⎦
is TU, but the matrix
⎡
⎣
0 1 1 0
−1 0 0 0
0 1 −1 1
⎤
⎦
is not (because the determinant of the submatrix
1 1
1 −1
equals −2).