An Extension of the Nested Partitions Method
EBERT BREA
Algorithm. The
Mixed

Integer

Nested

Partitions

Method
Initialization
Given:
the
number

of

real

components,

n;
the
number

of

integer

components,

m;
the
problem
minimize
z∈Rn×Zm
f(z),
subject

to
where
l
 z

 u,
l,

u

Rn

× Zm,

e.i.:

l

=

(l(1)),

.

.

.

,

l(n))
|
{z
}
n
;
¯l(n+1),

.

.

.

,

¯l(n+m)
|
{z
}
m
)t
and

u

=

(u(1)),

.

.

.

,

u(n))
|
{z
}
n
;
(n+1),

.

.

.

,

(n+m)
|
{z
}
m
)t;
the
number

Mσ(0) of

subregions

of

the

current

most

promising

region

σ(0)

=

Θ;
the
number

of

sample

points

Nj(k)

from

each

jth

subregion

σj(k)

at

each

kth

iteration;
Choose:
an
ε(i) R+ for

each

i

∈ {1,

.

.

.

,

n};
an
ε¯(i) N for

each

i

∈ {n

+

1,

.

.

.

,

n

+

m},

what

allows

us

to

define

the

expected

maximum

depth

of

the

mixed
integer

vector,

ε

=

(1),

.

.

.

,

ε(n)
|
{z
}
n
;
ε¯(n+1),

.

.

.

,

ε¯(n+m)
|
{z
}
m
)t
Rn+ × Nm;
Declare:
the
mixed

integer

depth

vector

d(k)

=

(d(1)(k),

.

.

.

,

d(n)(k)
|
{z
}
n
;
(n+1)(k),

.

.

.

,

(n+m)(k)
|
{z
}
m
)t;
Let k
=

0;
Calculate:
the
initial

mixed

integer

depth

vector,

e.i.,

d(0)

=

D(0,

n,

m,

σ(0),

Θ),

of

the

promising

region

σ(0);
while ε
 d(k)

do
Partitioning
Partition
the

current

promising

region

σ(k)

into

j(k)}Mσ(k)

j=1
subregion;
Aggregate
the

current

surrounding

region

σMσ(k)+1 (k)

=

Θ

\ σ(k),

and

denote

it

as

S(σ(k));
Random Sampling
Execute
the

Sampling

Procedure

for

taking

Nj(k)

random

points

from

each

jth

subregion

j(k)}Mσ(k)
j=1
,
namely:
for

each

jth

subregion,

get

the

set

of

sampled

points

j,s}Nj

(k);
s=1
Execute
the

Sampling

Procedure

for

also

taking

Nσ(k)+1(k)

random

points

from

surrounding

region
NMσ(k)+1
σMσ(k)+1 (k),
that

is,

for

getting

Mσ(k)+1,s}
s=1
(k)
;
Measuring
Calculate
the

performance

of

each

got

sampled

points

using

the

objective

function

f(θ),

namely:

f(θ)|θ
j,s
for
jth

subregion

at

each

sth

random

sampling,

and

also

the

sampled

points

from

the

surrounding

region
σMσ(k)+1 (k);
Estimating
Estimate
the

promising

region,

that

is,

finding

the

index

of

the

best

performance,

namely,

first

estimate
I(σˆ
j(k))

=

min

s∈{1,...,Nj
}
f(θj,s),
and
then
ˆjk
=
min
j∈{1,...,Mσ(k)+1}
I(σˆ
j(k)).
In
the

case

that

two

or

more

regions

are

equally

promising,

the

tie

can

be

randomized

broken.
Decision
if ˆjk
≤ Mσ(k) then
Let σ(k
+

1)

=

σˆ (k);
jk
Update by
using

d(k

+

1)

=

D(k

+

1,

n,

m,

σ(k

+

1),

Θ);
Let k
← k

+

1;
else
Backtrack
to

the

entire

feasible

region

Θ;
Let k
← 0;
Let σ(k)
=

Θ;
Update by
using

d(0)

=

D(0,

n,

m,

σ(k),

Θ);
Figure 8.
The MINP method
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930
124