Algoritmos Heurísticos para la Solución del Problema Lineal con Restricciones de Equilibrio (Heuristic Algorithms for Solving Linear Problems with Equilibrium Constraints)
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 comple...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cátedra UNESCO en Gestión de Información en las Organizaciones (La Habana)
2016-03-01
|
| Series: | GECONTEC: Revista Internacional de Gestión del Conocimiento y la Tecnología |
| Subjects: | |
| Online Access: | https://www.upo.es/revistas/index.php/gecontec/article/view/1918 |
| _version_ | 1797716510797463552 |
|---|---|
| author | Dania Tamayo-Vera Gemayqzel Bouza-Allende Antonio Bolufé-Röhler |
| author_facet | Dania Tamayo-Vera Gemayqzel Bouza-Allende Antonio Bolufé-Röhler |
| author_sort | Dania Tamayo-Vera |
| collection | DOAJ |
| description | 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 abstract
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. |
| first_indexed | 2024-03-12T08:22:30Z |
| format | Article |
| id | doaj.art-3ae3c04634bf4df88c36284d229cd565 |
| institution | Directory Open Access Journal |
| issn | 2255-5684 |
| language | English |
| last_indexed | 2024-03-12T08:22:30Z |
| publishDate | 2016-03-01 |
| publisher | Cátedra UNESCO en Gestión de Información en las Organizaciones (La Habana) |
| record_format | Article |
| series | GECONTEC: Revista Internacional de Gestión del Conocimiento y la Tecnología |
| spelling | doaj.art-3ae3c04634bf4df88c36284d229cd5652023-09-02T18:20:16ZengCátedra UNESCO en Gestión de Información en las Organizaciones (La Habana)GECONTEC: Revista Internacional de Gestión del Conocimiento y la Tecnología2255-56842016-03-0141Algoritmos Heurísticos para la Solución del Problema Lineal con Restricciones de Equilibrio (Heuristic Algorithms for Solving Linear Problems with Equilibrium Constraints)Dania Tamayo-VeraGemayqzel Bouza-AllendeAntonio Bolufé-RöhlerLos 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 abstract 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.https://www.upo.es/revistas/index.php/gecontec/article/view/1918Problemas con Restricciones de EquilibrioProblemas con Restricciones de ComplementariedadAlgoritmos HeurísticosOptimizaciónLinear Equilibrium Constrained ProblemsMathematical Program with Complementarity Constraints |
| spellingShingle | Dania Tamayo-Vera Gemayqzel Bouza-Allende Antonio Bolufé-Röhler Algoritmos Heurísticos para la Solución del Problema Lineal con Restricciones de Equilibrio (Heuristic Algorithms for Solving Linear Problems with Equilibrium Constraints) GECONTEC: Revista Internacional de Gestión del Conocimiento y la Tecnología Problemas con Restricciones de Equilibrio Problemas con Restricciones de Complementariedad Algoritmos Heurísticos Optimización Linear Equilibrium Constrained Problems Mathematical Program with Complementarity Constraints |
| title | Algoritmos Heurísticos para la Solución del Problema Lineal con Restricciones de Equilibrio (Heuristic Algorithms for Solving Linear Problems with Equilibrium Constraints) |
| title_full | Algoritmos Heurísticos para la Solución del Problema Lineal con Restricciones de Equilibrio (Heuristic Algorithms for Solving Linear Problems with Equilibrium Constraints) |
| title_fullStr | Algoritmos Heurísticos para la Solución del Problema Lineal con Restricciones de Equilibrio (Heuristic Algorithms for Solving Linear Problems with Equilibrium Constraints) |
| title_full_unstemmed | Algoritmos Heurísticos para la Solución del Problema Lineal con Restricciones de Equilibrio (Heuristic Algorithms for Solving Linear Problems with Equilibrium Constraints) |
| title_short | Algoritmos Heurísticos para la Solución del Problema Lineal con Restricciones de Equilibrio (Heuristic Algorithms for Solving Linear Problems with Equilibrium Constraints) |
| title_sort | algoritmos heuristicos para la solucion del problema lineal con restricciones de equilibrio heuristic algorithms for solving linear problems with equilibrium constraints |
| topic | Problemas con Restricciones de Equilibrio Problemas con Restricciones de Complementariedad Algoritmos Heurísticos Optimización Linear Equilibrium Constrained Problems Mathematical Program with Complementarity Constraints |
| url | https://www.upo.es/revistas/index.php/gecontec/article/view/1918 |
| work_keys_str_mv | AT daniatamayovera algoritmosheuristicosparalasoluciondelproblemalinealconrestriccionesdeequilibrioheuristicalgorithmsforsolvinglinearproblemswithequilibriumconstraints AT gemayqzelbouzaallende algoritmosheuristicosparalasoluciondelproblemalinealconrestriccionesdeequilibrioheuristicalgorithmsforsolvinglinearproblemswithequilibriumconstraints AT antonioboluferohler algoritmosheuristicosparalasoluciondelproblemalinealconrestriccionesdeequilibrioheuristicalgorithmsforsolvinglinearproblemswithequilibriumconstraints |