optimización combinatoria
La optimización combinatoria es un subcampo de la optimización matemática que consiste en encontrar un objeto óptimo a partir de un conjunto finito de objetos, [1] donde el conjunto de soluciones factibles es discreto o puede reducirse a un conjunto discreto. Los problemas típicos de optimización combinatoria son el problema del viajante de comercio ("TSP"), el problema del árbol de expansión mínimo ("MST") y el problema de la mochila . En muchos de estos problemas, como los mencionados anteriormente, la búsqueda exhaustivano es tratable, por lo que en su lugar se debe recurrir a algoritmos especializados que descartan rápidamente gran parte del espacio de búsqueda o algoritmos de aproximación.
La optimización combinatoria está relacionada con la investigación de operaciones , la teoría de algoritmos y la teoría de la complejidad computacional . Tiene aplicaciones importantes en varios campos, incluida la inteligencia artificial , el aprendizaje automático , la teoría de subastas , la ingeniería de software , las matemáticas aplicadas y la informática teórica .
Cierta literatura de investigación [2] considera que la optimización discreta consiste en la programación de enteros junto con la optimización combinatoria (que a su vez se compone de problemas de optimización relacionados con estructuras gráficas ), aunque todos estos temas tienen literatura de investigación estrechamente entrelazada. A menudo implica determinar la forma de asignar eficientemente los recursos utilizados para encontrar soluciones a problemas matemáticos. [ aclaración necesaria ]
Existe una gran cantidad de literatura sobre algoritmos de tiempo polinomial para ciertas clases especiales de optimización discreta. Una parte considerable de ella está unificada por la teoría de la programación lineal . Algunos ejemplos de problemas de optimización combinatoria que se cubren en este marco son los caminos más cortos y los árboles de camino más corto , flujos y circulaciones , árboles de expansión , emparejamiento y problemas de matroides .
Para problemas de optimización discreta NP-completos , la literatura de investigación actual incluye los siguientes temas:
Los problemas de optimización combinatoria pueden verse como la búsqueda del mejor elemento de algún conjunto de elementos discretos; por lo tanto, en principio, se puede utilizar cualquier tipo de algoritmo de búsqueda o metaheurística para resolverlos. Quizás los enfoques [ palabras de comadreja ] más universalmente aplicables son ramificar y enlazar (un algoritmo exacto que se puede detener en cualquier momento para servir como heurístico), ramificar y cortar (usa optimización lineal para generar límites), dinámica programación (una construcción de solución recursiva con ventana de búsqueda limitada) y búsqueda tabú(un algoritmo de intercambio de tipo codicioso). Sin embargo, no se garantiza que los algoritmos de búsqueda genéricos encuentren primero una solución óptima, ni que se ejecuten rápidamente (en tiempo polinomial). Dado que algunos problemas de optimización discretos son NP-completos , como el problema (de decisión) del viajante de comercio, [7] esto se espera a menos que P=NP .
