60
4 Layout of a Single Floor
is equivalent to
w i
h i
≤ ρ i and
h i
w i
≤ ρ i ,
which can be expressed as the linear constraints
w i ≤ ρ i h i and h i ≤ ρ i w i .
The nonoverlap constraints (4.8) are disjunctive and nonconvex by their very
nature, and they are the hardest to enforce. Much of the rest of this chapter is
concerned with ways to handle these constraints. If the relative position of each pair
of departments is known, then constraints (4.8) can be written as linear inequalities,
and the formulation becomes a convex optimization problem that is straightforward
to solve. This observation motivates the two-stage approaches presented in Sect. 4.4.
We recall that this formulation locates the centre of the facility at the origin,
while other models locate the bottom left-hand corner at the origin. This difference
changes the mathematical details slightly but is otherwise of no consequence.
4.2 Mixed-Integer Second-Order Conic Optimization
Formulation
We present in this section a mixed-integer second-order conic optimization (MISOCO) formulation of the UA-FLP that uses binary variables to linearize the
nonoverlap constraints (4.8). Specifically, we define four binary variables for each
pair of departments. For all 1 ≤ i ≤ n and 1 ≤ j ≤ n, let
α ij =
1 if i is to the left of j , i.e., i precedes j in the horizontal dimension
0 otherwise,
β ij =
1 if i is below j , i.e., i precedes j in the vertical dimension
0 otherwise.
These definitions are illustrated in Fig. 4.2.
i
j
i j = 1
j
i
i j = 1
Fig. 4.2 We set α ij = 1 when department i is to the left of j , and β ij = 1 when department i is
below j
4 Layout of a Single Floor
is equivalent to
w i
h i
≤ ρ i and
h i
w i
≤ ρ i ,
which can be expressed as the linear constraints
w i ≤ ρ i h i and h i ≤ ρ i w i .
The nonoverlap constraints (4.8) are disjunctive and nonconvex by their very
nature, and they are the hardest to enforce. Much of the rest of this chapter is
concerned with ways to handle these constraints. If the relative position of each pair
of departments is known, then constraints (4.8) can be written as linear inequalities,
and the formulation becomes a convex optimization problem that is straightforward
to solve. This observation motivates the two-stage approaches presented in Sect. 4.4.
We recall that this formulation locates the centre of the facility at the origin,
while other models locate the bottom left-hand corner at the origin. This difference
changes the mathematical details slightly but is otherwise of no consequence.
4.2 Mixed-Integer Second-Order Conic Optimization
Formulation
We present in this section a mixed-integer second-order conic optimization (MISOCO) formulation of the UA-FLP that uses binary variables to linearize the
nonoverlap constraints (4.8). Specifically, we define four binary variables for each
pair of departments. For all 1 ≤ i ≤ n and 1 ≤ j ≤ n, let
α ij =
1 if i is to the left of j , i.e., i precedes j in the horizontal dimension
0 otherwise,
β ij =
1 if i is below j , i.e., i precedes j in the vertical dimension
0 otherwise.
These definitions are illustrated in Fig. 4.2.
i
j
i j = 1
j
i
i j = 1
Fig. 4.2 We set α ij = 1 when department i is to the left of j , and β ij = 1 when department i is
below j