Algoritmos Heurísticos para la Solución del Problema Lineal con Restricciones de Equilibrio

• Dania Tamayo-Vera ^[1] ; Gemayqzel Bouza-Allende ^[1] ; Antonio Bolufé-Röhler ^[1]
  1. [1] Universidad de La Habana

     Universidad de La Habana

     Cuba

     
• Localización: GECONTEC: revista Internacional de Gestión del Conocimiento y la Tecnología, ISSN-e 2255-5684, Vol. 4, Nº. 1, 2016, págs. 46-57
• Idioma: español
• Títulos paralelos:
  • Heuristic Algorithms for Solving Linear Problems with Equilibrium Constraints
• Enlaces
  • Texto completo
• Resumen
  • español

    Los problemas lineales con restricciones de equilibrio son un caso particular de los modelos de optimización con restricciones de equilibrio. Debido a la complejidad que presentan, la condición de equilibrio se sustituye por condiciones necesarias obteniéndose un problema con restricciones de complementariedad (MPCC). La estructura del conjunto de soluciones factibles del MPCC obtenido es compleja ya que es la unión de poliedros. Resolver todos los problemas correspondientes a minimizar la función objetivo sobre cada uno de estos poliedros es computacionalmente costoso. El presente trabajo utiliza un enfoque heurístico para dar solución al MPCC, adaptando los algoritmos de Búsqueda Local y Recocido Simulado. Este trabajo presenta un conjunto de funciones de prueba y los resultados computacionales más significativos obtenidos.

  • English

    Linear equilibrium constrained programming is a special class of optimization models with equilibrium constraints. Because of the complexity of the equilibrium condition it is replaced by necessary conditions, which leads to a complementarity constrained problem (MPCC). The set of feasible solutions in a MPCC is structured as a union of polyhedrons. Solving the MPCC problem would require the minimization of the objective function on each of these polyhedrons. The computation cost of this approach is unfeasible, thus, this work presents a new approach where heuristic algorithms such as Hill Climbing and Simulated Annealing are used to search for good solutions on the polyhedrons space. A new benchmark for linear equilibrium constrained optimization is introduced. The computational results achieved by the proposed heuristics on the new benchmark are presented.

• Referencias bibliográficas
  • Aussel, D., Bendotti, P. y Pištěk, M. (2016). Nash Equilibrium in Pay-as-bid Electricity Market: Part 1Existence and Characterisation. To...
  • Boschetti, M.A., Maniezzo, V., Roffilli, M., y Bolufé-Röhler A.B. (2009). Matheuristics: Optimization, Simulation and Control. Hybrid Metaheuristics....
  • Bouza, G. (2006). Mathemaical Programs with Equilibrium Constrainst: Solution Techniques from Parametric Optimization. Universiteit Twente.
  • Deb, K. y Agrawal, S. (1999) Understanding interactions among genetic algorithm parameters. Foundations of Genetic Algorithms, 265–286.
  • Ehrenmann, A. (2004). Equilibrium Problems with Equilibrium Constraints and their Application to Electricity Markets. Fitzwilliam College.
  • Fukushima, M. and Lin, G. H. (2003). New relaxation method for mathematical programs with complementarity constraints. Journal of Optimization...
  • Kirkpatrick, S. (1984). Optimization by simulated annealing: Quantitative studies. Journal of Statistical Physics, 34(5):975–986
  • Larrañaga P. y Lozano, J. A. (2002). Estimation of distribution algorithms: A new tool for evolutionary computation. Springer Verlag.
  • Luo Z. Q., Pang J. S. y Ralph D. (1996). Mathematical Programs with Equilibrium Constraints. Cambridge University Press.
  • Luo, Z. Q., Pang, J. S. y Ralph, D. (2006). Equilibrium constrained optimization problems. European Journal on Operational Research, 169(13):1108–1128.
  • Migdalas, A. (1995). Bilivel programming in traffic planning: Models, methods and challenge. Journal of Global Optimization, 7: 381-405.
  • Scholtes, S. and Scheel, H. (2000). Mathematical programs with complementarity constraints: Stationarity, optimality and sensitivity. Mathematics...
  • Talbi, E (2009). Metaheuristics: from design to implementation. John Wiley & Sons.
  • Tamayo-Vera, D., Bouza G. y Bolufé-Röhler A. (2016). Benchmark for the LEC optimization problem. DOI: 10.13140/RG.2.1.1719.1288. (https://www.researchgate.net/...
  • Ye, J. (1999). Optimality conditions for optimization problems with complementarity constraints. SIAM Journal on Optimization, 9(2):374–387.