Fecha
de

recepción:

12/11/2021
Fecha
de

aceptación:

17/04/2022
Pp.
116


Pp.

141
An Extension of the Nested Partitions Method
Ebert Brea
ebrea@ucab.edu.ve
Centro de Investigación y Desarrollo de Ingeniería & Escuela de Ingeniería Industrial,
Universidad Católica Andrés Bello, Caracas, Venezuela
Abstract
This
article

addresses

a

new

extension

of

the

well

known

Nested

Partitions

(NP)

method

for

globally

solving

mixed
integer
nonlinear

optimization

problems

under

bound

constraints.

The

extension,

called

Mixed

Integer

Nested
Partitions
(MINP)

method,

is

based

on

the

same

stages

of

the

NP

method

at

each

iteration,

i.e.:

partitioning;
random
sampling;

identifying

of

the

promising

region,

which

presumes

to

contain

at

least

a

global

solution

of

the
problem;
and

verifying

of

the

stopping

rule.

Nevertheless,

both

a

new

scheme

of

partitioning

and

a

stopping

rule
proposal
are

here

presented

as

main

contributions

to

mixed

integer

programming.

The

article

has

also

included
a
theoretical

study

of

the

behavior

of

the

MINP

method

from

the

point

of

view

of

the

Markov

chain.

Numerical
examples
have

made

sure

the

correct

functionality

of

the

algorithmic

method

and

its

new

stopping

rule.
Key words:
Nested

Partitions

method,

mixed

integer

nonlinear

programming,

global

optimization.
Una Extensión del Método de Particiones Anidadas
Resumen
Este
artículo

aborda

una

nueva

extensión

del

conocido

método

de

Particiones

Anidadas

(PA)

para

resolver
globalmente
problemas

de

optimización

no

lineales

enteros

mixtos

bajo

restricciones

de

bandas.

La

extensión,
llamada
método

de

Particiones

Anidadas

Enteros

Mixtos

(PAEM),

se

basa

en

las

mismas

etapas

del

método
PA
en

cada

iteración,

es

decir:

partición;

muestreo

aleatorio;

identificación

de

la

región

prometedora,

que
presume
contener

al

menos

una

solución

global

del

problema;

y

verificación

de

la

regla

de

parada.

Sin

embargo,
tanto
un

nuevo

esquema

de

partición

como

una

propuesta

de

regla

de

parada

que

se

presentan

aquí

son

las
principales
contribuciones

a

la

programación

entera

mixta.

El

artículo

también

ha

incluido

un

estudio

teórico

del
comportamiento
del

método

PAEM

desde

el

punto

de

vista

de

la

cadena

de

Markov.

Ejemplos

numéricos

han
asegurado
la

correcta

funcionalidad

del

método

algorítmico

y

su

nueva

regla

de

parada.
Palabras clave:
método

de

Particiones

Anidadas,

programación

no

lineal

entera

mixta,

optimización

global.
Uma Extensão do Método de Partições Aninhadas
Resumo
Este
artigo

aborda

uma

nova

extensão

do

conhecido

método

de

Partições

Aninhadas

(PA)

para

resolver
globalmente
problemas

de

otimização

não

linear

de

inteiros

mistos

com

restrições.

A

extensão,

chamada

método
de
Partições

Aninhadas

Inteiras

Mistas

(PAIM),

é

baseada

nos

mesmos

estágios

do

método

PA

em

cada

iteração:
particionamento;
amostragem

aleatória;

identificação

da

região

promissora,

que

presume

conter

pelo

menos
uma
solução

global

do

problema;

e

verificação

do

critério

de

parada.

Não

obstante,

tanto

um

novo

esquema

de
particionamento
como

uma

proposta

de

critério

de

parada

são

aqui

apresentados

como

principais

contribuições
à
programação

inteira

mista.

O

artigo

também

incluiu

um

estudo

teórico

do

comportamento

do

método

PAIM
do
ponto

de

vista

da

cadeia

de

Markov.

Exemplos

numéricos

garantem

o

correto

funcionamento

do

método
algorítmico
e

do

novo

critério

de

parada.
Palavras chave:
Método

de

Partições

Aninhadas,

programação

não

linear

inteira

mista,

otimização

global.
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930