An Extension of the Nested Partitions Method

Una Extensión del Método de Particiones Anidadas

Resumen

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.