An Extension of the Nested Partitions Method
EBERT BREA
Definition 6 (Depth vector)
Let

d(k)

denote

the

kth
mixed
integer

depth

vector

of

the

current

kth

promising
region.
It

is

then

said

that

d(k)

=

uσ lσ,

i.e.,
d(k)
=

u
(1)
σ(k)
l
(1)
σ(k),...,u
(n+m)
σ(k)
l
(n+m)
σ(k)
t
,k ∈−N.
(4)
Note
that

according

to

above

definitions:

i)

σ(0)

is

the
feasible
region

Θ

of

Problem

1;

ii)

the

kth

promising
region
σ(k)

is

a

convex

hull,

which

is

bounded

by
lσ(k)
−

z −uσ(k),

and

it

will

hereafter

be

simplified

its
notation
by

lσ −

z −uσ;

and

iii)

σ(k)

=

SM
σ
i=1
σi(k).
Finally,
let

κ ∈−N be

the

cumulative

counter

iterations
that
are

executed

by

the

MINP

method,

which

always
is
greater

than

or

equal

to

k.
b.
ON

THE

PARTITIONS

OF

THE

PROMISING
REGION
We
now

turn

our

attention

to

the

proposed

procedure

of
partitioning
of

the

kth

promising

region

σ(k),

which

is
based
on

a

novel

method

for

getting

the

boundaries

of
each
ith

subregion

σi(k)

in

the

current

promising

mixed
integer
region,

as

is

shown

in

Figure

18

on

page

135.
Proposition 1
Let

σ(j)(k)

=

{x ∈−R

:

l
(j)
σ
≤−x ≤−u
(j)
σ
}
be
the

jth

interval

of

real

number

or

set

of

the

jth
real
value

component

that

defines

the

current

promising
mixed
integer

region

σ(k)

∈−Zm.

Then,

an

adequate
partition
of

the

jth

component

of

σ(j)(k)

into

two

disjoint
subsets
is

given

by
σ
(j)
1
(k)

=

{x ∈−R

:

l(j)
(j)
2
σ
≤−x ≤−
δ(j)
σ
};
(5a)
σ
(k)

=

{y ∈−R

:

δ(j)
σ
< y ≤−u(j)
σ
},
(5b)
where
δ
(j)
σ
=

(l
(j)
σ
+

u
(j)
σ
)/2

is

the

midpoint

of

the

rect
line
segment

defined

by

both

l
(j)
σ
and

u
(j)
σ
.
Proof. We
know

that

a

partition

of

an

integer

number

set
into
two

subsets

must

then

yield

two

disjoint

subsets

and
the
union

of

both

subsets

must

contain

all

elements

of
the
original

set.
As
can

be

seen:

first,

σ
(j)
1
(k)σ2(j)(k)

=

,

and

second,
σ(j)(k)
=

σ
(j)
1
(k)

∪−σ
(j)
2
(k),

what

has

allowed

us

to
partition
the

set

σ(j)(k)

properly.
Proposition 2
Let

σ¯(j)(k)

=

{y ∈−Z

:

¯l
(j)
σ
≤−

y ≤−u¯
(j)
σ

}
be
the

jth

interval

of

integer

number

or

set

of

the
jth
integer

value

component

that

defines

the

current
promising
mixed

integer

region

σ(k

∈−Zm.

Then,

an
appropriate
partition

of

the

jth

component

of

σ¯(j)(k)

into
two
disjoint

subsets

is

given

by



lσ(j)(j)]
[δ(j)

+1,u¯
(j)
σ
],

if

δ()⌋−=

δ();
lσ(j),δ()]
[δ(),u¯
(j)
σ
],

if

δ()⌋−

6
=

δ(),
(6)
where
δ
σ(j)
=

l
(j)
σ
+

u¯
(j)
σ
)/2

is

the

midpoint

of

the

rect
line
segment

defined

by

¯l
(j)
σ
and

u¯
(j)
σ
.
Proof.
Because

we

have

two

cases,

the

first

one,
when
δ(j)

=

lσ(j)

+

u¯(σj))/2

is

an

integer

number,

and
the
second

one,

when

δ(j)

is

a

no

integer

number,

these
cases
will

separately

be

proved.
Part
i)

if

δ(j)

is

an

integer

number,

i.e.,

δ()⌋−=

δ()
the
set

given

by

σ¯(j)(k)

=

{y ∈−Z

:

¯lσ(j)

≤−

y ≤−u¯(σj)}
can
be

partitioned

into

two

subsets,

namely,

σ¯
{y ∈−Z
(j)
1
(k)

=
:

¯lσ(j)

≤−

y ≤−

δ(j)}−

and

σ¯(j)
2
(k)

=

{y ∈−Z

:

δ(j)

+
1
≤−

y ≤−u¯
(j)
σ
},

where

both

mentioned

subsets

indeed
are
disjoint,

i.e.,

σ¯
(j)
1
(k)

∩−σ¯
(j)
2
(k)

=

,

and

σ¯(j)(k)

=
σ¯1
(j)
(k)¯σ2

(j)
(k).
Part
ii)

In

the

case

when

δ(j)

is

a

no

integer

number,
then
the

subsets

σ¯
(j)
1
(k)

=

{y ∈−Z

:

¯l
(j)
σ
≤−

y ≤−

δ(j)⌋}
and
σ¯
(j)
2
(k)

=

{y ∈−Z

:

δ(j)⌉−≤−

y ≤−u¯
(j)
σ
}−

are

such

that
σ¯
(j)
1
(k)σ¯
(j)
2
(k)

=

,

and

σ¯(j)(k)

=

σ¯
(j)
1
(k)σ¯
(j)
2
(k).
Based
on

Propositions

1

and

2,

it

was

designed

Parti-
tioning
procedure

shown

in

Figure

18.
Remark 1
Assume,

without

any

loss

of

generality,

that
Partitions
procedure

in

Figure

18

is

conducted

on

any
kth
promising

region

σ(k)

for

solving

Problem

1,

as

a
result
of

Propositions

1

and

2.

Then

Partitions

procedure
yields
Mσ

=

2n+m

disjoint

subregions

from

the

current
promising
region

σ(k).
Proof.
Due

to

the

fact

that

according

to

Partitioning
procedure
in

Figure

18,

at

each

kth

iteration,

both

each
of
the

n real

components

is

divided

by

into

2

subsets

and
each
of

the

m integer

components

is

also

divided

into

2
subsets,
yielding

respectively

at

each

iteration

2n and

2m
subsets,
thus,

this

fact

allows

us

to

obtain

Mσ

=

2n+m.
As
can

be

seen

from

Partitions

procedure

in

Figure

18,
at
each

kth

iteration

a

set

of

{σi(k)}Mi=1σ

subregions

from
the
current

promising

region

σ(k)

are

mutually

disjoint
subsets,
i.e.,

σi(k)

∩−σi(k)

=

∅−

for

all

i

6=

j

and

i,j
{}Mℓ=1σ
,

and

moreover

σ(k)

=

SM
σ
i=1

σi(k).
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930
121