Problemas de Optimización Combinatoria

La Optimización Combinatoria es una rama de la optimización. Su dominio se compone de problemas de optimización donde el conjunto de posibles soluciones es discreto o se puede reducir a un conjunto discreto.

A la hora de tratar con problemas de optimización combinatoria, el objetivo consiste en encontrar la mejor solución posible existente o solución óptima, aquella que minimiza una función de coste dada .

Si el problema no es complejo existen técnicas para resolver dichos problemas, como el Branch and Bound, Branch and Cut, etc. A medida que la complejidad del espacio de búsqueda aumenta, el coste de ejecución de dichos algoritmos puede aumentar de forma exponencial, convirtiendo la resolución en prácticamente inviable.

Otra posibilidad para afrontar este tipo de problemas, consiste en buscar una solución subóptima, pero en un tiempo razonable. En algunos casos es posible encontrar incluso la solución óptima al problema.

Este tipo de técnicas se pueden dividir en dos grandes grupos:

  • Heurísticas

  • Metaheurísticas

Además de estos grupos, está surgiendo en la actualidad une nueva tecnología que se puede usar para este tipo de problemas, la tecnología de Razonamiento Basado en Casos o CBR (Case Based Reasoning).

Heurísticas

Las técnicas heurísticas son algoritmos que encuentran soluciones de buena calidad para problemas combinatorios complejos explotando el conocimiento del dominio de aplicación. Los algoritmos heurísticos son fáciles de implementar y encuentran buenas soluciones con esfuerzos computacionales relativamente pequeños; sin embargo, renuncian (desde el punto de vista teórico) a encontrar la solución óptima global de un problema. En problemas de gran tamaño rara vez un algoritmo heurístico encuentra la solución óptima global.

Metaheurísticas

Los algoritmos metaheurísticos son algoritmos de propósito general, que no dependen del problema, y que ofrecen buenos resultados pero que normalmente no acaban ofreciendo “la” solución óptima sino soluciones subóptimas. Se acostumbran a utilizar para aquellos problemas en que no existe un algoritmo o heurística específicos que los resuelva, o bien
cuando no es práctico implementar dichos métodos.


Algorithms Classification

Figura basada en la siguiente imagen de la wikipedia