An Extension of the Nested Partitions Method
EBERT BREA
i
.
INTRODUCTION
Consider
the
following
bound
constrained
mixed
integer
nonlinear
minimization
problem:
Problem 1
minimize
z
∈
R
n
×
Z
m
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
R
n
×−
Z
m
;
f
(
z
)
:
R
n
×−
Z
m
→−
R
is
a
nonlinear
function,
for
which
analytical
and
explicit
mathematical
expression
cannot
be
obtained;
and
l,u
∈−
R
n
×−
Z
m
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
R
n
×−
Z
m
.
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
pro
gramming
through
a
rigorous
study
presented
in
[4
,
5
]
.
For
his
part,
Brea
has
found
optimum
solutions
for
the
design
of
equipment
mak
ing
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
globall
y
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
algo
rithms,
it
can
be
included:
Genetic
Al-
gorithms
[12,
13]
;
Ant
Colony
[14]
;
Pa
rticle
Swarm
optimization,
and
Artificial
Bee
Colony
[15]
,
whereas
in
the
group
of
non
bio-inspired
meta
heuristic
algorithms,
we
have:
Si
mulated
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
gl
obally
solving
mixed
integer
optimiza-
tion
problems
[19]
,
which
is
base
d
on
a
hybrid
of
the
Nested
Par
titions
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É
N
o
25.1
Semestre
octubre-febrero
2022
ISSN
electrónico:
2790-5195
ISSN:
1316-3930
117