4.4 Two-Stage Approaches
65
4.4 Two-Stage Approaches
Two-stage approaches for the UA-FLP do not guarantee to find the global optimal
solution. They are a compromise by which we sacrifice the ability to achieve
guaranteed global optimality for the sake of being able to compute good solutions
for large-scale instances. We lose the guarantee because the first stage finds a local
(not necessarily global) minimum.
The first stage determines the relative positions of the departments in a desirable
layout. In other words, the output of the first stage allows us to fix the values of the
binary variables in the formulation in Sect. 4.2 or to fix the sequence-pairs in the
formulation in Sect. 4.3.
The second stage uses the information from the first stage to determine the actual
layout. The formulations in Sects. 4.2 and 4.3 become SOCOs after the binary
variables are fixed, and such problems can be solved efficiently to global optimality
by state-of-the-art commercial solvers.
The quality of a two-stage approach can be estimated by taking instances for
which we know the optimal value (and perhaps one or more corresponding optimal
layouts) and comparing this information to the best results obtained using the twostage approach.
4.4.1 First Stage: Method Based on Nonlinear Optimization
In the next sections we describe two methods for the first stage. The first method
relies on a nonlinear optimization problem, and the second uses a genetic algorithm.
The nonlinear optimization method handles the nonoverlapping requirement
indirectly by penalizing overlap in the objective function. The idea is to use an
attractor–repeller paradigm in which the objective function combines an attractor
component and a repeller component:
• The attractor component is a function that seeks to make the distances between
departments as small as possible by attracting all pairs of departments to each
other. This component aims for a total distance of zero, i.e., a solution in which
all the departments have their centres at the same point and thus fully overlap.
• The repeller component counteracts the effect of the attractor by seeking to
enforce nonoverlap. It can take different forms, and the general idea is that the
more the departments overlap, the higher the value of the repeller component.
Specifically, let
D ij = (x i − x j )
2
+ (y i − y j )
2
65
4.4 Two-Stage Approaches
Two-stage approaches for the UA-FLP do not guarantee to find the global optimal
solution. They are a compromise by which we sacrifice the ability to achieve
guaranteed global optimality for the sake of being able to compute good solutions
for large-scale instances. We lose the guarantee because the first stage finds a local
(not necessarily global) minimum.
The first stage determines the relative positions of the departments in a desirable
layout. In other words, the output of the first stage allows us to fix the values of the
binary variables in the formulation in Sect. 4.2 or to fix the sequence-pairs in the
formulation in Sect. 4.3.
The second stage uses the information from the first stage to determine the actual
layout. The formulations in Sects. 4.2 and 4.3 become SOCOs after the binary
variables are fixed, and such problems can be solved efficiently to global optimality
by state-of-the-art commercial solvers.
The quality of a two-stage approach can be estimated by taking instances for
which we know the optimal value (and perhaps one or more corresponding optimal
layouts) and comparing this information to the best results obtained using the twostage approach.
4.4.1 First Stage: Method Based on Nonlinear Optimization
In the next sections we describe two methods for the first stage. The first method
relies on a nonlinear optimization problem, and the second uses a genetic algorithm.
The nonlinear optimization method handles the nonoverlapping requirement
indirectly by penalizing overlap in the objective function. The idea is to use an
attractor–repeller paradigm in which the objective function combines an attractor
component and a repeller component:
• The attractor component is a function that seeks to make the distances between
departments as small as possible by attracting all pairs of departments to each
other. This component aims for a total distance of zero, i.e., a solution in which
all the departments have their centres at the same point and thus fully overlap.
• The repeller component counteracts the effect of the attractor by seeking to
enforce nonoverlap. It can take different forms, and the general idea is that the
more the departments overlap, the higher the value of the repeller component.
Specifically, let
D ij = (x i − x j )
2
+ (y i − y j )
2