An Extension of the Nested Partitions Method
EBERT BREA
i.
INTRODUCTION
Consider
the

following

bound

constrained

mixed

integer
nonlinear
minimization

problem:
Problem 1
minimize
zRn×Zm
f(z);
(1a)
subject
to
l −
z −u,
(1b)
where:
z

will

henceforward

denote

any

mixed

integer
vector,
i.e.,

z =

(z(1),...,z(n);z(n+1),...,z(n+m))t,

in
the
(n+m)-multidimensional

Euclidean

space

Rn ×−Zm;
f(z)
:

Rn ×−Zm

→−R

is

a

nonlinear

function,

for

which
analytical
and

explicit

mathematical

expression

cannot
be
obtained;

and

l,u ∈−Rn ×−Zm

respectively

are

both
the
lower

and

upper

bounds

of

the

mixed

integer

feasible
region
Θ.
Note
that

we

have

here

denoted

by

the

symbol

−

for
indicating
that

a

vector

precedes

to

another

vector,

what
will
be

defined

later.
In
this

case,

the

objective

function

must

be

evaluated

by
an
appropriate

simulation

model

or

by

solving

a

nonlin-
ear
system

equations,

and

besides

the

objective

function
has
no

gradient

function,

because

the

objective

function
domain
is

defined

in

the

set

mixed

integer

Rn ×−Zm.
Nowadays
this

kind

of

problems

has

had

an

important
presence
in

the

industry,

due

to

fact

the

enormous
challenges
facing

the

industry,

which

must

find

answers
for
efficiently

designing

equipment

and

systems,

and
therefore
friendly

with

the

environment,

and

at

the

same
time
taking

into

account

the

economic

sustainability.
Examples
of

these

problems

in

the

branch

of

chemical
engineering
are

presented

by

Floudas

[1],

who

intro-
duces
an

important

number

of

mixed

integer

nonlin-
ear
optimization

problems

on:

design,

scheduling

and
planning
of

batch

processes;

heat

exchanger

network
synthesis,
etc.

Grossmann

and

Kravanja

also

present
an
overview

of

the

applications

in

many

areas

within

the
engineering
process

[2, 3].

Tawarmalani

and

Sahinidis
also
address

the

mixed

integer

nonlinear

programming
through
a

rigorous

study

presented

in

[4,

5 ].

For

his
part,
Brea

has

found

optimum

solutions

for

the

design

of
equipment
making

use

of

the

mixed

integer

optimization
viewpoint
[6, 7],

and

he

also

has

developed

a

new

meta-
heuristic
based

on

a

game

framework

of

random

pattern
search
algorithms,

offering

a

new

approach

for

globally
solving
mixed

integer

nonlinear

problems

[8,

9,

10] .
Another
example

worthwhile

of

commenting,

it

is

the
recently
published

article

by

Kantor

and

coworkers,

who
propose
a

model

for

finding

an

integrated

solution,

which
allows
the

industry

to

provide

optimum

integral

solutions
within
plants

and

potential

industrial

symbiosis

options,
using
a

mixed

integer

linear

programming

approach

[11].
There
exists

a

vast

amount

of

algorithmic

optimization
methods
via

a

wide

variety

metaheuristic

approaches
for
globally

solving

constrained

and

unconstrained

mixed
integer
nonlinear

optimization

problems,

which

could

be
grouped
in

two

large

classes,

namely:

the

bio-inspired
metaheuristic
algorithms

and

the

non

bio-inspired

meta-
heuristic
algorithms.

Among

the

bio-inspired

meta-
heuristic
algorithms,

it

can

be

included:

Genetic

Al-
gorithms
[12,

13] ;

Ant

Colony

[14];

Particle

Swarm
optimization,
and

Artificial

Bee

Colony

[15],

whereas

in
the
group

of

non

bio-inspired

metaheuristic

algorithms,
we
have:

Simulated

Annealing

[16];

Branch-and-Bound
method
[17],

Nested

Partitions

method

[18];

Game

of
Patterns
[9],

etc.
The
best

of

our

knowledge,

there

exists

only

one

pub-
lished
article

concerning

an

extension

the

Nested

Parti-
tions
method

for

globally

solving

mixed

integer

optimiza-
tion
problems

[19],

which

is

based

on

a

hybrid

of

the
Nested
Partitions

method

[18, 20] and

the

well

known
CPLEX
[21].

Nevertheless,

we

here

propose

a

new

ex-
tension
of

the

Nested

Partitions

method

for

finding

global
solutions
to

bound

constrained

mixed

integer

nonlinear
optimization
problems

based

on

the

main

idea

of

the
Nested
Partitions,

namely:

partition

of

the

promising
region;
sampling

of

each

subregion

from

partitioned
promising
region

and

the

surrounding

region

to

the
promising
region;

and

identification

of

the

next

promising
region,
which

presumes

to

have

a

global

solution

of
our
problem.

Nonetheless,

the

algorithmic

extension,
which
has

been

called

Mixed

Integer

Nested

Partitions
(MINP)
method

includes:

both

a

novel

partitions

scheme
and
a

new

algorithm

stopping

rule

represent

the

main
contributions
of

this

article.
Numerical
examples

have

allowed

us

to

assert

that
the
MINP

method

has

successfully

identified

promising
regions,
in

a

relative

small

amount

of

iterations.

Nev-
ertheless,
the

MINP

method

has

resulted

to

be

a

very
expensive
method,

from

the

viewpoint

of

times

the

ob-
jective
function

requires

to

be

evaluated

by

the

algorithm
for
globally

solving

this

kind

of

problems.
Due
to

the

fact

that

the

MINP

method

has

resulted

to

be
an
expensive

algorithm

from

the

viewpoint

of

the

number
of
function

evaluations

for

identifying

at

least

a

global
solution,
we

have

therefore

considered

to

undertake

fur-
thermore
research

in

the

future,

for

hybridizing

the

MINP
method
with

some

local

search

method,

e.g.,

the

mixed
integer
randomized

pattern

search

algorithm

developed
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930
117