4.1 Nonconvex Continuous Optimization Formulation
59
1
2 w i
1
2 w j
x j − x i
1
2 h j
1
2
h i
y i − y j
Fig. 4.1 Diagram showing that the nonoverlap constraints must ensure that either |y i − y j | ≥
1
2 (h i + h j ) or |x i − x j | ≥
1
2 (w i + w j )
The last three sets of constraints enforce the location requirements. Constraints
(4.6) and (4.7) ensure that the departments are placed entirely inside the facility.
Constraints (4.8) prevent overlapping by forcing the separation of each pair of
departments in (at least) one direction (see Fig. 4.1).
The area constraints (4.4) are bilinear (not linear), and they have been traditionally modelled using linearization approaches (see Sect. 4.6). Alternatively, they
can be handled directly using conic optimization. Both approaches rely on the
observation that these constraints can be relaxed to
w i h i ≥ A i ,
(4.9)
which has the advantage of being convex. Moreover, this relaxed form can be
formulated as a semidefinite constraint,
h i
√
A i
√
A i w i
0
(4.10)
or, equivalently, as a second-order cone constraint (see Appendix A),
w i + h i ≥
w i − h i
2
√
A i
2
.
(4.11)
Because the optimization will push this relaxed form towards equality, in the optimal
solution w i h i will be close to or equal to A i . Moreover, it is straightforward to check
that if
n
i=1 A i = h F w F , then any one of the relaxed forms (4.9), (4.10), and (4.11)
suffices to ensure that (4.4) holds at every feasible solution.
Constraints (4.5) enforce the maximum aspect ratio; it is straightforward to write
each of them as two linear inequality constraints:
max
w i
h i
,
h i
w i
≤ ρ i
59
1
2 w i
1
2 w j
x j − x i
1
2 h j
1
2
h i
y i − y j
Fig. 4.1 Diagram showing that the nonoverlap constraints must ensure that either |y i − y j | ≥
1
2 (h i + h j ) or |x i − x j | ≥
1
2 (w i + w j )
The last three sets of constraints enforce the location requirements. Constraints
(4.6) and (4.7) ensure that the departments are placed entirely inside the facility.
Constraints (4.8) prevent overlapping by forcing the separation of each pair of
departments in (at least) one direction (see Fig. 4.1).
The area constraints (4.4) are bilinear (not linear), and they have been traditionally modelled using linearization approaches (see Sect. 4.6). Alternatively, they
can be handled directly using conic optimization. Both approaches rely on the
observation that these constraints can be relaxed to
w i h i ≥ A i ,
(4.9)
which has the advantage of being convex. Moreover, this relaxed form can be
formulated as a semidefinite constraint,
h i
√
A i
√
A i w i
0
(4.10)
or, equivalently, as a second-order cone constraint (see Appendix A),
w i + h i ≥
w i − h i
2
√
A i
2
.
(4.11)
Because the optimization will push this relaxed form towards equality, in the optimal
solution w i h i will be close to or equal to A i . Moreover, it is straightforward to check
that if
n
i=1 A i = h F w F , then any one of the relaxed forms (4.9), (4.10), and (4.11)
suffices to ensure that (4.4) holds at every feasible solution.
Constraints (4.5) enforce the maximum aspect ratio; it is straightforward to write
each of them as two linear inequality constraints:
max
w i
h i
,
h i
w i
≤ ρ i