Ebert Brea

doi:10.62876/tekhne.v25i1.5209

Autores/as

Ebert Brea Universidad Católica Andrés Bello https://orcid.org/0000-0002-6897-0893

DOI:

https://doi.org/10.62876/tekhne.v25i1.5209

Palabras clave:

método de particiones anidadas, programación no lineal entera mixta, optimización global

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.

Descargas

Los datos de descargas todavía no están disponibles.

Biografía del autor/a

Ebert Brea, Universidad Católica Andrés Bello

Ebert Brea currently is a Full Professor of both the School of
Electrical Engineering at the Universidad Central de Venezuela (UCV), and the School of Industrial Engineering at the Universidad Católica Andrés Bello (UCAB). He is also a Research Associate at the Centro de Investigación y Desarrollo de Ingeniería of the UCAB. He received his PhD from the Department of Mathematics of the University of Southampton, the UK, a MSc in Operational Research and a five-year BSc degree in Electrical Engineering, both from the Faculty of Engineering of the UCV. His research interests include: development and study of (meta)heuristic optimization algorithms; optimization by simulation; Monte Carlo simulation; and development of simulation models of discrete event dynamic systems.

Citas

C. A. Floudas. Nonlinear and mixed-integer optimization: fundamentals and applications. New York, NY, USA: Oxford Univ. Press, 1995.

I. E. Grossmann y Z. Kravanja, "Mixed-Integer Nonlinear Programming: A Survey of Algorithms and Applications", en Mixed-Integer Nonlinear Programming, New York, NY, USA: Springer, jun. 1997, pp. 73-100. DOI: https://doi.org/10.1007/978-1-4612-1960-6_5

I. E. Grossmann, "Review of Nonlinear Mixed-Integer and Disjunctive Programming Techniques", Optim. Eng., vol. 3, no. 3, pp. 227-252, 2002. DOI: https://doi.org/10.1023/A:1021039126272

M. Tawarmalani y N. V. Sahinidis. Convexification and global optimization in continuous and mixed-integer nonlinear programming: theory, algorithms, software, and applications. Dordrecht, The Netherlands: Kluwer Academic Publishers, 2002.

M. Tawarmalani y N. V. Sahinidis, "Global optimization of mixed-integer nonlinear programs: A theoretical and computational study", Math. Program., vol. 99, no. 3, pp. 563-591, 2004. DOI: https://doi.org/10.1007/s10107-003-0467-6

E. Brea, "Extensiones del método de Nelder Mead a problemas de variables enteras y enteras mixtas", tech. rep., Univ. Central de Venezuela, Caracas, Venezuela, sep. 2009.

E. Brea, "Una extensión del método de Nelder Mead a problemas de optimización no lineales enteros mixtos", Rev. Int. Métodos Numéricos Cálculo Diseño Ing., vol. 29, pp. 163-174, jul. 2013. DOI: https://doi.org/10.1016/j.rimni.2013.06.005

E. Brea, "On the Performance of the Mixed Integer Randomized Pattern Search Algorithm", en 13th Int. Congr. Numerical Methods Eng. Appl. Sci., Y. González et al., Eds., Caracas, Venezuela, jul. 2016, pp. 61-72.

E. Brea, "Game of Patterns: An approach for solving mixed integer nonlinear optimization problems", en Int. Congr. Ind. Eng. Oper. Manage. (IEOM 2017), Bogota, Colombia, abr. 2017. [En línea]. Disponible en: http://ieomsociety.org/bogota2017/proceedings

E. Brea, "On the mixed integer randomized pattern search algorithm", Rev. Unión Matemáticos Argentinos, vol. 60, pp. 485-503, sep. 2019. DOI: https://doi.org/10.33044/revuma.v60n2a14

I. Kantor, J.-L. Robineau, H. Bütün y F. Maréchal, "A mixed-integer linear programming formulation for optimizing multi-scale material and energy integration", Frontiers in Energy Res., vol. 8, pp. 49.1-49.20, abr. 2020. DOI: https://doi.org/10.3389/fenrg.2020.00049

H. Jalota y M. Thakur, "Genetic Algorithm Designed for Solving Linear or Nonlinear Mixed-Integer Constrained Optimization Problems", en Int. Proc. Adv. Soft Comput. Intell. Syst. Appl., Singapore, dic. 2018, pp. 277-290. DOI: https://doi.org/10.1007/978-981-10-5272-9_27

K. Deep, K. P. Singh, M. Kansal y C. Mohan, "A real coded genetic algorithm for solving integer and mixed integer optimization problems", Appl. Math. Comput., vol. 212, pp. 505-518, jun. 2009. DOI: https://doi.org/10.1016/j.amc.2009.02.044

M. Schlüter, J. A. Egea y J. R. Banga, "Extended ant colony optimization for non-convex mixed integer nonlinear programming", Comput. Oper. Res., vol. 36, pp. 2217-2229, jul. 2009. DOI: https://doi.org/10.1016/j.cor.2008.08.015

M. Mohammadi, S. N. Musa y A. Bahreininejad, "Optimization of mixed integer nonlinear economic lot scheduling problem with multiple setups and shelf life using metaheuristic algorithms", Adv. Eng. Softw., vol. 78, pp. 41-51, dic. 2014. DOI: https://doi.org/10.1016/j.advengsoft.2014.08.004

M. F. Cardoso, R. L. Salcedo, S. F. de Azevedo y D. Barbosa, "A simulated annealing approach to the solution of MINLP problems", Comput. Chem. Eng., vol. 21, pp. 1349-1364, abr. 1997. DOI: https://doi.org/10.1016/S0098-1354(97)00015-X

O. K. Gupta y A. Ravindran, "Branch and bound experiments in convex nonlinear integer programming", Manage. Sci., vol. 31, pp. 1533-1546, dic. 1985. [En línea]. Disponible en: http://www.jstor.org/stable/2631793

L. Shi y S. Ólafsson, "Nested Partitions method for global optimization", Oper. Res., vol. 48, pp. 390-407, may. 2000. DOI: https://doi.org/10.1287/opre.48.3.390.12436

L. Xia, Y. Zhao, M. Xie, J. Shao y J. Dong, "Mixed integer programming based nested partition algorithm for facility location optimization problems", en 2008 IEEE Int. Conf. Service Oper. Logistics Informatics, oct. 2008, vol. 2, pp. 2375-2381.

L. Shi y S. Ólafsson. Nested Partitions Method, Theory and Applications. 1st ed., New York, NY, USA: Springer, 2009. DOI: https://doi.org/10.1007/978-0-387-71909-2

IBM. ILOG CPLEX Optimization Studio interfaces. ago. 2021. [En línea]. Disponible en: https://www.ibm.com/analytics/

L. Shi y S. Ólafsson, "Stopping rules for the stochastic Nested Partitions method", Methodology Comput. Appl. Probability, vol. 2, pp. 37-58, abr. 2000. DOI: https://doi.org/10.1023/A:1010055101140

R. Cheng. Non-standard parametric statistical inference. 1st ed., Oxford, U.K.: Oxford Univ. Press, 2017.

L. de Haan, "Estimation of the Minimum of a Function Using Order Statistics", J. Amer. Statist. Assoc., vol. 76, pp. 467-469, jun. 1981. [En línea]. Disponible en: http://www.jstor.org/stable/2287851

E. Brea, "Game of Patterns and Genetic Algorithms under a comparative study", en Hybrid Metaheuristics, HM2019, M. B. Aguilera et al., Eds., Concepcion, Chile, ene. 2019, vol. 11299, pp. 93-107. DOI: https://doi.org/10.1007/978-3-030-05983-5_7

C. Audet y J. E. Dennis Jr., "Pattern Search Algorithms for Mixed Variable Programming", SIAM J. Optim., vol. 11, pp. 573-594, jul. 2001. DOI: https://doi.org/10.1137/S1052623499352024

B. Adenso-Díaz y M. Laguna, "Fine-Tuning of Algorithms Using Fractional Experimental Designs and Local Search", Oper. Res., vol. 54, pp. 99-114, feb. 2006. DOI: https://doi.org/10.1287/opre.1050.0243

C.-H. Chen, D. He, M. Fu y L. H. Lee, "Efficient Simulation Budget Allocation for Selecting an Optimal Subset", INFORMS J. Comput., vol. 20, pp. 579-595, may. 2008. DOI: https://doi.org/10.1287/ijoc.1080.0268

J. Berkhout, "An accelerated stopping rule for the Nested Partition Hybrid Algorithm for discrete stochastic optimization", Discrete Event Dyn. Syst., vol. 25, pp. 441-452, sep. 2015. DOI: https://doi.org/10.1007/s10626-014-0191-9