2.3 Mixed-Integer Linear Optimization Approach
9
where Π n is the set of all permutations π of {1, 2, . . . , n} and d n
ij is the centre-tocentre distance between departments i and j measured with respect to permutation
π. This formulation is compact and elegant but not particularly useful in practice.
Nevertheless, it provides an important insight, which is that the SRFLP is an
optimization problem over all possible permutations of n departments.
An important observation here is that if π denotes the permutation symmetric to
π, defined by π
i = π n+1−i , i = 1, . . . , n, then d π
ij = d π
ij . In other words, for a given
layout, the order of the departments can be reversed without changing the value
of the objective function. This means that it is possible (and important) to apply
symmetry-breaking techniques that reduce the computational cost of mathematical
optimization algorithms for the SRFLP.
2.3 Mixed-Integer Linear Optimization Approach
Let us recall the formulation (2.3–2.5) but now expressed for n departments:
minimize
n−1
i=1
n
j =i+1
c ij |x i − x j |,
(2.7)
subject to |x i − x j | ≥
1
2
(( i + j ), i, j = 1, . . . , n, i < j,
(2.8)
1
2
i ≤ x i ≤ L −
1
2
i , i = 1, . . . , n.
(2.9)
In line with the observations in Sect. 2.1.1, we will derive a more efficient
formulation that is amenable to practical use.
2.3.1 Linearization of the Distance
We present two approaches to linearizing the objective function (2.7):
• The first approach linearizes |x i − x j | by defining new variables d ij := |x i − x j |
for i, j = 1, . . . , n, i < j, rewriting the objective as
min
x 1 ,...,x n
n−1
i=1
n
j =i+1
c ij d ij .
The objective function is now linear, but we must add constraints on d ij . Simply
adding d ij = |x i − x j | only shifts the nonlinearity from the objective to the
constraints and does not achieve much in practice. We instead take advantage of
9
where Π n is the set of all permutations π of {1, 2, . . . , n} and d n
ij is the centre-tocentre distance between departments i and j measured with respect to permutation
π. This formulation is compact and elegant but not particularly useful in practice.
Nevertheless, it provides an important insight, which is that the SRFLP is an
optimization problem over all possible permutations of n departments.
An important observation here is that if π denotes the permutation symmetric to
π, defined by π
i = π n+1−i , i = 1, . . . , n, then d π
ij = d π
ij . In other words, for a given
layout, the order of the departments can be reversed without changing the value
of the objective function. This means that it is possible (and important) to apply
symmetry-breaking techniques that reduce the computational cost of mathematical
optimization algorithms for the SRFLP.
2.3 Mixed-Integer Linear Optimization Approach
Let us recall the formulation (2.3–2.5) but now expressed for n departments:
minimize
n−1
i=1
n
j =i+1
c ij |x i − x j |,
(2.7)
subject to |x i − x j | ≥
1
2
(( i + j ), i, j = 1, . . . , n, i < j,
(2.8)
1
2
i ≤ x i ≤ L −
1
2
i , i = 1, . . . , n.
(2.9)
In line with the observations in Sect. 2.1.1, we will derive a more efficient
formulation that is amenable to practical use.
2.3.1 Linearization of the Distance
We present two approaches to linearizing the objective function (2.7):
• The first approach linearizes |x i − x j | by defining new variables d ij := |x i − x j |
for i, j = 1, . . . , n, i < j, rewriting the objective as
min
x 1 ,...,x n
n−1
i=1
n
j =i+1
c ij d ij .
The objective function is now linear, but we must add constraints on d ij . Simply
adding d ij = |x i − x j | only shifts the nonlinearity from the objective to the
constraints and does not achieve much in practice. We instead take advantage of