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
k
th
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
k
th
nonempty
promising
region
given
by
σ
(
k
)
=
{
z
∈−
R
n
×−
Z
m
:
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
k
th
baggy
hull
depth
vector
of
the
current
promising
region
σ
(
k
)
,
which
is
given
by
d
(
k
)˜
=
u
(1)
−
l
(1)
2
k
,...,
u
(
n
)
−
l
(
n
)
2
k
;
&
u
¯
(
n
+1)
−
¯
l
(
n
+1)
2
k
'
,...,
&
u
¯
(
n
+
m
)
−
¯
l
(
n
+
m
)
2
k
'!
t
(14)
Then
d
(
k
)˜
depicts
the
measurements
of
the
smallest
baggy
hull
in
R
n
×−
Z
m
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
j
th
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
k
th
iteration,
we
therefore
have
by
(5a)
and
(5b)
that
δ
(
j
)
σ
(
k
)
−
l
(
j
)
σ
(
k
)
≤
−
u
(
j
)
−
l
(
j
)
2
k
;
(15a)
u
(
j
)
σ
(
k
)
−
δ
σ
(
j
()
k
)
≤
−
u
(
j
)
−
l
(
j
)
2
k
,
(15b)
where
δ
σ
(
k
)
(
j
)
=
(
l
σ
(
k
)
(
j
)
+
u
σ
(
k
)
)
/
2
.
Secondly,
(
j
)
due
to
Proposition
2,
each
j
th
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
k
th
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
)
2
k
'
;
(16a)
u
¯
(
j
)
σ
(
k
)
−
δ
σ
(
j
()
k
)
−
1
≤
−
&
u
¯
(
j
)
−
¯
l
(
j
)
2
k
'
.
(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
)
2
k
'
;
(17a)
Revista
TEKHNÉ
N
o
25.1
Semestre
octubre-febrero
2022
ISSN
electrónico:
2790-5195
ISSN:
1316-3930
125