An Extension of the Nested Partitions Method
EBERT BREA
iv.
THE PSEUDOCODE OF THE MINP
METHOD
Taking
into

account

the

theoretical

main

results

above,

it
has
been

proposed

the

MINP

method,

which

is

shown

in
Figure
8

using

an

easy

description

of

its

source

code.
The
figure

shows:

the

preamble

of

the

algorithm,

in
which
given:

i)

the

problem;

ii)

a

chosen

expected

depth
vector;
and

iii)

a

declared

vector

d(k),

the

MINP

method
executes
iterative

loops

for

solving

Problem

1,

whilst

the
stopping
rule

has

not

been

met.
v.
ON THE MINP METHOD
In
this

section

we

study

the

main

properties

of

the

MINP
method
from

a

stochastic

viewpoint.

According

to

the
MINP
method,

it

is

reasonable

to

figure

up

that

the

MINP
method
generates

a

Markov

stochastic

process

on

a
countable
and

infinite

discrete

stochastic

state

space,
i.e.,
a

Markov

chain

that

can

be

described

by

a

set
of
{D(κ)}κ=0,

where

κ ∈−N here

depicts

a

cumulative
iteration
counter

of

the

MINP

method,

what

means

in

a
nonmathematical
language:

the

future

only

depends

on
today,
and

not

what

have

occurred

in

past

time
We
shall

therefore

turn

up

our

attention

to

the

Markov
chain
state

space

that

is

generated

by

the

MINP

method,
when
it

is

run

for

globally

solving

any

mixed

integer

prob-
lem
given

by

Problem

1.

However,

before

introducing

our
main
results

on

the

Markov

chain

that

is

generated

by

the
MINP
method

(MINPMC),

we

must

point

out

that

each
state
of

the

MINPMC

space

will

be

measured

by

a

depth
vector
of

the

kth

baggy

hull

of

the

current

promising
region
σ(k),

which

will

be

called

baggy

hull

depth

vector,
and
we

shall

then

be

defined

it

as

follows.
Definition 7 (Baggy hull of a promising region)
Let
σ(k)
be

a

kth

nonempty

promising

region

given

by
σ(k)
=

{z ∈−Rn ×−Zm :

lσ(k)

−

z −uσ(k)},

(13)
with
mixed

integer

depth

vector

d(k)

=

uσ(k)

−−

lσ(k).

It
says
to

be

a

baggy

hull

of

σ(k),

denoted

by

σ(k

,

is

the
smallest
oversized

hull

σ(k)

such

that

σ(k

⊇−σ(k).
Basing
on

this

last

definition,

we

thus

have

the

following
result.
Proposition 4
Let

d(k

be

the

kth

baggy

hull

depth
vector
of

the

current

promising

region

σ(k),

which

is
given
by
d(k
=

u(1)
l(1)
2k
,...,
u(n)
l(n)
2k
;
&
u¯(n+1)
¯l(n+1)
2k
'
,...,
&
u¯(n+m)
¯l(n+m)
2k
'!t
(14)
Then
d(k

depicts

the

measurements

of

the

smallest
baggy
hull

in

Rn ×−Zm

and

thus

d(k

−

d(k)

for

each
k ∈−N.
Proof.
For

proving

this

statement,

we

first

pay

attention
to
the

real

components,

and

later

to

the

integer

compo-
nents
of

the

promising

region

σ(k).
Because
of

Proposition

1,

each

jth

real

component

of
the
current

promising

region

σ(k)

has

successively

been
divided
by

2,

yielding

as

a

result

consecutive

partitions
into
two

subsets

per

each

kth

iteration,

we

therefore
have
by

(5a)

and

(5b)

that
δ
(j)
σ(k)
l
(j)
σ(k)

u(j)
l(j)
2k
;
(15a)
u
(j)
σ(k)
δσ(j()k)


u(j)
l(j)
2k
,
(15b)
where
δσ(k)

(j)
=

(lσ(k)

(j)
+uσ(k))/2.
Secondly,
(j)
due

to

Proposition

2,

each

jth

integer

compo-
nent
of

the

current

promising

region

σ(k)

has

succes-
sively
been

partitioned

into

a

pair

of

subsets,

consecu-
tively
generating

two

subsets

not

necessarily

the

same
size
per

each

kth

iteration,

hence,

by

(6)

we

know

that
if
δ
(j)
σ(k)
=

l
(j)
σ(k)

+

u¯
δσ(j()k)⌋−=
(j)
σ(k))/2
is

an

integer

number,

i.e.,
δσ(j()k),

then
δ
(j)
σ(k)
¯l
(j)
σ(k)

&
u¯(j)
¯l(j)
2k
'
;
(16a)
u¯
(j)
σ(k)
δσ(j()k)

1


&
u¯(j)
¯l(j)
2k
'
.
(16b)
Whereas,
if

δ
(j)
σ(k)
is
a

non

integer

number,

i.e.,

δσ(j()k)⌋−

6
=
δσ(j()k),
then
δσ(j()k)⌋−¯l
(j)
σ(k)

&
u¯(j)
¯l(j)
2k
'
;
(17a)
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930
125