An Extension of the Nested Partitions Method
EBERT BREA
objective
function

value

comes

from

σ2(1),

what

allows
us
to

identify

the

subregion

σ2(1)

as

the

next

promising
region,
namely,

σ(2)

=

σ2(1).
S(σ(2))
σ2(1)
=

σ(2)
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
x(1)
x(2)
Figure 7.
promising region σ(2)
This
procedure

is

recurrently

carried

out

until

some
stopping
criterion

is

met.
Shi
and

Ólafsson

have

proposed

two

stopping

rules
for
the

NP

method,

namely:

the

first

one

is

based

on
ordinal
optimization

concepts;

and

the

second

one

has
been
developed

applying

concepts

of

order

statistics

for
objective
function

values

[22].
iii.
THE MIXED INTEGER NESTED
PARTITIONS METHOD
The
MINP

method

has

been

designed

for

globally

solv-
ing
mixed

integer

bound

constrained

nonlinear

problems.
For
that,

we

have

developed

the

MINP

method

based
on
similarity

stages

to

the

NP

method,

namely:

i)

parti-
tioning
of

the

promising

region

σ(k)

into

Mσ

subregion
σi(k)
for

all

i ∈−

{}Mℓ=1σ

;

ii)

sampling

of

the

subregion
σi(k)
by

random

mixed

integer

trial

points

from

each
subregion;
iii)

identifying

of

the

next

promising

region
σ(k +
1)

=

σˆi(k),

where

ˆi denotes

the

index

where

the
best
value

of

the

objective

function

has

come

from;

iv)
verifying
whether

the

MINP

method

will

go

next

iteration
or
it

will

stop,

and

as

a

result

of

this

verifying

stage,

i.e.,
the
algorithm

will

accordingly

test

at

each

iteration,

if

the
stopping
rule

is

met.
a.
PRELIMINARIES
This
subsection

deals

with

some

definitions

for

famil-
iarizing
the

reader

with

concepts

and

notations

that
have
been

included

both

in

the

explanation

of

the

MINP
method
and

its

pseudocode.
Definition 1 (Precedent vector)
Let

z1

and

z2

be

two
mixed
integer

vectors,

i.e.,

z1,z2

∈−Rn ×−Zm.

It

is

said
that
z1

precedes

z2

in

order,

and

will

be

denoted

by
z1
−

z2,

if

their

respective

components

z
each
(i)
1
≤−

z
(i)
2
for
i ∈−

{}n+m
=1
.
Definition 2 (Subsequent vector)
Let

z1

and

z2

be

two
mixed
integer

vectors,

i.e.,

z1,z2

∈−Rn ×−Zm.

It

is

said
that
z1

succeeds

z2

in

order,

and

will

be

denoted

by
z1
−

z2,

if

their

respective

components

z
each
(i)
1
≥−

z
(i)
2
for
i ∈−

{}n+m
=1
.
The
relationship

between

the

vectors

that

have

been
defined
above

are

respectively

called

strictly

precedes
or
strictly

succeeds,

if

the

above

inequalities

are

true

as
strict
inequalities

for

all

ith

components

of

z1

and

z2.
Definition 3 (Promising region)
Let

σ(k)

be

a
nonempty
promising

region

at

the

current

iteration

k
of
the

MINP

method.

It

is

then

said

that

σ(k)

is

given

by
σ(k)

=

{z ∈−Rn ×Zm :

lσ(k)

−

z −uσ(k)}, k ∈−N,

(3)
where:
k hereafter

depicts

the

counter

of

iteration

that
has
been

carried

out

by

the

MINP

method

from

the

initial
promising
region

σ(0)

=Θ=

{z ∈−Rn ×Zm :

l −

z −u};
lσ(k),uσ(k)
∈−Rn ×−Zm

respectively

are

the

lower

and
upper
bound

vector

of

the

kth

promising

region

σ(k),
which
presumes

to

contain

at

least

a

global

solution

of
Problem
1.
Note
that

according

to

Definition

3,

each

kth

promising
region
must

be

a

nonempty,

because

it

presumes

to
contain
at

least

a

global

solution

of

Problem

1.

Moreover,
the
smallest

promising

region,

in

the

number

of

element
sense,
that

is

contained

on

the

feasible

region

of

Prob-
lem
1,

is

a

singleton

set.
Definition 4 (Subregion)
Let

σi(k)

denote

the

ith

sub-
region
of

the

current

kth

promising

region.

It

is

then
said
that

σi(k)

⊂−σ(k)

for

each

i ∈−

{}Mℓ=1σ

,

and

σi(k)


σj(k)
=

∅−

for

all

i

6=

j

and

i,j ∈−

{}Mℓ=1σ

,

where

Mσ
denotes
the

number

of

subregion.
Definition 5 (Surrounding region)
Let

S(σ(k))

be

the
surrounding
region

to

the

kth

promising

region

σ(k).

It
is
then

said

that

S(σ(k))

=

σ(0)\σ(k).
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930
120