
143Nested Partitions for Large-Scale Optimization
2. Select partitioning and sampling variables. For each free binary
variable in qm, compute the following probability based on
and
.
Pr pqm
p
y
p
y
p
pqm
y
p
y
p
.
11
ρ
ρ
ρ
ρ
−−
′
∈
−
′
−
′
∑
∀∈/
Here ρ ≥ 1 so that a larger value of ρ leads to a higher probability
of selecting a variable with a smaller gap between its corresponding
and
. Sort all binary variables in qm in the descending order of
Pr
p
. Select the top one or several binary variables in qm as the next
partitioning variables (qp), and the next one or several binary vari-
ables as the sampling variables (qs).
3. Partitioning. Partition the current ...