48
3 Layout on Several Rows
3.4.2 Integer Linear Optimization Model
In this section we present an integer linear optimization (ILO) model for the
MREFLP. The approach used here takes advantage of the structure induced by the
fact that all the department lengths are equal, and the result is a formulation in which
all the variables are binary. In fact, much stronger results can be proved about the
MREFLP, and they allow us to build much tighter models than those for the general
MRFLP.
The information about the column-wise relative position of pairs i,j of departments is incorporated into the model using the following variables:
ξ ij =
1, if departments i and j are assigned to the same column
0, otherwise.
We also recall again the betweenness variables from Sect. 2.4. For three distinct
departments i, j , and k, we have
β ij k =
1, if department k lies between departments i and j
0, otherwise.
Note that the definition of β ij k counts all departments k between i and j regardless
of which row k is in. Recall that by Theorem 3.3, we can fill up the C columns and
m rows with spacing departments. This means that for each column between i and
j , there are precisely m departments counted as being between i and j .
We can now formulate the MREFLP as an ILO problem:
minimize
i
⎛
⎝
1
m
k =i,j
β ij k + (1 − ξ ij )
⎞
⎠
(3.66)
s.t. β ij h + β ikh + β jkh ≤ 2, i < k < j, h = i, j, k,
(3.67)
− β ij h + β ikh + β jkh + β ij k ≥ 0, i < k < j, h = i, j, k,
(3.68)
β ij h − β ikh + β jkh + β ikj ≥ 0, i < k < j, h = i, j, k,
(3.69)
β ij h + β ikh − β jkh + β jki ≥ 0, i < k < j, h = i, j, k,
(3.70)
ξ hk − β ij h + β ikh + β jkh ≥ 0, i < k < j, h = i, j, k,
(3.71)
ξ hj + β ij h − β ikh + β jkh ≥ 0, i < k < j, h = i, j, k,
(3.72)
ξ hi + β ij h + β ikh − β jkh ≥ 0, i < k < j, h = i, j, k,
(3.73)
ξ ij + β ikj + β ij k + β jki ≤ 1, i < k < j,
(3.74)
ξ ik + β ikj + β ij k + β jki ≤ 1, i < k < j,
(3.75)
3 Layout on Several Rows
3.4.2 Integer Linear Optimization Model
In this section we present an integer linear optimization (ILO) model for the
MREFLP. The approach used here takes advantage of the structure induced by the
fact that all the department lengths are equal, and the result is a formulation in which
all the variables are binary. In fact, much stronger results can be proved about the
MREFLP, and they allow us to build much tighter models than those for the general
MRFLP.
The information about the column-wise relative position of pairs i,j of departments is incorporated into the model using the following variables:
ξ ij =
1, if departments i and j are assigned to the same column
0, otherwise.
We also recall again the betweenness variables from Sect. 2.4. For three distinct
departments i, j , and k, we have
β ij k =
1, if department k lies between departments i and j
0, otherwise.
Note that the definition of β ij k counts all departments k between i and j regardless
of which row k is in. Recall that by Theorem 3.3, we can fill up the C columns and
m rows with spacing departments. This means that for each column between i and
j , there are precisely m departments counted as being between i and j .
We can now formulate the MREFLP as an ILO problem:
minimize
i
⎛
⎝
1
m
k =i,j
β ij k + (1 − ξ ij )
⎞
⎠
(3.66)
s.t. β ij h + β ikh + β jkh ≤ 2, i < k < j, h = i, j, k,
(3.67)
− β ij h + β ikh + β jkh + β ij k ≥ 0, i < k < j, h = i, j, k,
(3.68)
β ij h − β ikh + β jkh + β ikj ≥ 0, i < k < j, h = i, j, k,
(3.69)
β ij h + β ikh − β jkh + β jki ≥ 0, i < k < j, h = i, j, k,
(3.70)
ξ hk − β ij h + β ikh + β jkh ≥ 0, i < k < j, h = i, j, k,
(3.71)
ξ hj + β ij h − β ikh + β jkh ≥ 0, i < k < j, h = i, j, k,
(3.72)
ξ hi + β ij h + β ikh − β jkh ≥ 0, i < k < j, h = i, j, k,
(3.73)
ξ ij + β ikj + β ij k + β jki ≤ 1, i < k < j,
(3.74)
ξ ik + β ikj + β ij k + β jki ≤ 1, i < k < j,
(3.75)