4.2 Mixed-Integer Second-Order Conic Optimization Formulation
61
Furthermore, recall that d
x
ij and d
y
ij represent the horizontal and vertical distances
between i and j . Using these variables, we obtain the following MISOCO formulation:
minimize
1≤i
x
ij + d
y
ij )
(4.12)
s.t. d
x
ij ≥ x i − x j , d
x
ij ≥ x j − x i , 1 ≤ i < j ≤ n,
(4.13)
d
y
ij ≥ y i − y j , d
y
ij ≥ y j − y i , 1 ≤ i < j ≤ n,
(4.14)
h
min
i
≤ h i ≤ h
max
i , 1 ≤ i ≤ n,
(4.15)
w
min
i
≤ w i ≤ w
max
i
, 1 ≤ i ≤ n,
(4.16)
w i + h i ≥
w i − h i
2
√
A i
2
, 1 ≤ i ≤ n
(4.17)
w i ≤ ρ i h i and h i ≤ ρ i w i , 1 ≤ i ≤ n,
(4.18)
1
2
(w i − w F ) ≤ x i ≤
1
2
(w F − w i ), 1 ≤ i < j ≤ n,
(4.19)
1
2
(h i − h F ) ≤ y i ≤
1
2
(h F − h i ), 1 ≤ i < j ≤ n,
(4.20)
x i +
1
2
w i ≤ x j −
1
2
w j + w F (1 − α ij ), 1 ≤ i = j ≤ n,
(4.21)
y i +
1
2
h i ≤ y j −
1
2
h j + h F (1 − β ij ), 1 ≤ i = j ≤ n,
(4.22)
α ij + α ji + β ij + β ji = 1, 1 ≤ i < j ≤ n,
(4.23)
α ij , β ij ∈ {0, 1}, 1 ≤ i, j ≤ n.
(4.24)
Several constraints in this formulation are similar to those in the formulation of
Sect. 4.1. The objective function (4.12) and constraints (4.13) and (4.14) provide
a linearization of the objective function (4.1) by applying the first linearization
approach described in Sect. 2.3.1 to each of the x and y directions. Constraints
(4.15) and (4.16) are unchanged and enforce the lower and upper bounds on the
height and width of department i. Constraints (4.17) are the relaxed form of the area
constraints (4.4), and constraints (4.18) are the unchanged aspect ratio constraints.
Constraints (4.19) and (4.20) are slightly rewritten forms of (4.6) and (4.7).
The last four sets of constraints are the new nonoverlap constraints. Constraints
(4.23) require that for each pair i, j of departments, precisely one of the four
corresponding binary variables must be equal to 1 (and the other three must be
0). Constraints (4.21) and (4.22) are linearized versions of (4.8) that enforce the
nonoverlap requirement for i and j corresponding to the binary variable set to 1.
Finally, constraints (4.24) require α ij and β ij to be binary.
61
Furthermore, recall that d
x
ij and d
y
ij represent the horizontal and vertical distances
between i and j . Using these variables, we obtain the following MISOCO formulation:
minimize
1≤i
x
ij + d
y
ij )
(4.12)
s.t. d
x
ij ≥ x i − x j , d
x
ij ≥ x j − x i , 1 ≤ i < j ≤ n,
(4.13)
d
y
ij ≥ y i − y j , d
y
ij ≥ y j − y i , 1 ≤ i < j ≤ n,
(4.14)
h
min
i
≤ h i ≤ h
max
i , 1 ≤ i ≤ n,
(4.15)
w
min
i
≤ w i ≤ w
max
i
, 1 ≤ i ≤ n,
(4.16)
w i + h i ≥
w i − h i
2
√
A i
2
, 1 ≤ i ≤ n
(4.17)
w i ≤ ρ i h i and h i ≤ ρ i w i , 1 ≤ i ≤ n,
(4.18)
1
2
(w i − w F ) ≤ x i ≤
1
2
(w F − w i ), 1 ≤ i < j ≤ n,
(4.19)
1
2
(h i − h F ) ≤ y i ≤
1
2
(h F − h i ), 1 ≤ i < j ≤ n,
(4.20)
x i +
1
2
w i ≤ x j −
1
2
w j + w F (1 − α ij ), 1 ≤ i = j ≤ n,
(4.21)
y i +
1
2
h i ≤ y j −
1
2
h j + h F (1 − β ij ), 1 ≤ i = j ≤ n,
(4.22)
α ij + α ji + β ij + β ji = 1, 1 ≤ i < j ≤ n,
(4.23)
α ij , β ij ∈ {0, 1}, 1 ≤ i, j ≤ n.
(4.24)
Several constraints in this formulation are similar to those in the formulation of
Sect. 4.1. The objective function (4.12) and constraints (4.13) and (4.14) provide
a linearization of the objective function (4.1) by applying the first linearization
approach described in Sect. 2.3.1 to each of the x and y directions. Constraints
(4.15) and (4.16) are unchanged and enforce the lower and upper bounds on the
height and width of department i. Constraints (4.17) are the relaxed form of the area
constraints (4.4), and constraints (4.18) are the unchanged aspect ratio constraints.
Constraints (4.19) and (4.20) are slightly rewritten forms of (4.6) and (4.7).
The last four sets of constraints are the new nonoverlap constraints. Constraints
(4.23) require that for each pair i, j of departments, precisely one of the four
corresponding binary variables must be equal to 1 (and the other three must be
0). Constraints (4.21) and (4.22) are linearized versions of (4.8) that enforce the
nonoverlap requirement for i and j corresponding to the binary variable set to 1.
Finally, constraints (4.24) require α ij and β ij to be binary.