An Extension of the Nested Partitions Method
EBERT BREA
Procedure. Partitioning(n, m, Θ, σ, d(k))
Given:
the
number

of

real

components,

n;
the
number

of

integer

components,

m;
the
bounded

feasible

region

Θ,

namely:
l(i) ≤−x(i) ≤−u(i),
∀i ∈−

{1,

.

.

.

, n},
¯l(i) ≤−
y(i) ≤−u¯(i),

∀i ∈−

{1,

.

.

.

, m};
the
promising

region

σ ⊆−Θ

to

be

partitioned,

which

is

defined

by
lσ(i) ≤−x(i) ≤−u(iσ ),
∀i ∈−

{1,

.

.

.

, n},
¯lσ(i) ≤−
y(i) ≤−u¯(iσ ),

∀i ∈−

{1,

.

.

.

, m};
the
mixed

integer

depth

vector

of

the

current

promising

region

σ(k)

to

be

partitioned
dt(k)

=

(d(1)(k),

.

.

.

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

.

.

.

, d¯(n+m)(k)
|
{z
}
m
);
Let
Mσ =

2n+m be

the

number

of

subregions

to

be

denoted

by

j}Mj=1σ

;
Declare:
a
matrix

X =

[x(ij)]2Mσ,n
i=1,j=1
∈−R2Mσ×n for

saving

real

boundary

components

of

the

set

j}Mj=1σ

;
∈−Z2Mσ×m for
a
matrix

Y =

[y(ij)]2Mσ,m
i=1,j=1
saving

integer

boundary

components

of

the

set

j}Mj=1σ

;
Let
q =

1

be

the

counter

of

subregion

σj;
Initialization
Let
i =

1;
for q ←−
0

to Mσ −−

1

do
(b(n+m−1), b(n+m−2),
.

.

.

, b(0))2 ←−

c(q),

where

c(q)

is

a

convertor

function,

which

transforms

decimal
numbers

to

binary

numbers,

namely,

(b(n+m−1), b(n+m−2),

.

.

.

, b(0))2 ∈−

{0, 1}n+m;
for ℓ ←−
1

to n do
if u(ℓσ ) −−
lσ(ℓ) > ε(ℓ) then
δ(ℓ) =
(lσ(ℓ) +

u(ℓσ ))/2;
if b(ℓ−1) =
0

then
x(i,ℓ) ←−
lσ(ℓ);
x(i+1,ℓ) ←−
δ(ℓ);
else
x(i,ℓ) ←−
δ(ℓ);
x(i+1,ℓ) ←−u(ℓσ );
for ℓ ←−n +
1

to n +

m do
if u¯(ℓσ ) −−
¯lσ(ℓ) > ε¯(ℓ) then
δ(ℓ) =
(¯lσ(ℓ) +

(ℓσ ))/2;
if (b(ℓ−1) =
0)

∧−

(⌊δ(ℓ)⌋−=

⌈δ(ℓ)⌉)

then
y(i,ℓ−n) ←−
¯lσ(ℓ);
y(i+1,ℓ−n) ←−
δ(ℓ);
if (b(ℓ−1) =
1)

∧−

(⌊δ(ℓ)⌋−=

⌈δ(ℓ)⌉)

then
y(i,ℓ−n) ←−
δ(ℓ) +

1;
y(i+1,ℓ−n) ←−u¯(ℓσ );
if (b(ℓ−1) =
0)

∧−

(⌊δ(ℓ)⌋−

6=

⌈δ(ℓ)⌉)

then
y(i,ℓ−n) ←−
¯lσ(ℓ);
y(i+1,ℓ−n) ←−
⌊δ(ℓ)⌋;
if (b(ℓ−1) =
1)

∧−

(⌊δ(ℓ)⌋−

6=

⌈δ(ℓ)⌉)

then
y(i,ℓ−n) ←−
⌈δ(ℓ)⌉;
y(i+1,ℓ−n) ←−u¯(ℓσ );
Let
i ←−

i +

2
Figure 18.
Partitioning procedure
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930
135