La optimización combinatoria es un campo de la teoría de la optimización en matemáticas aplicadas asociado con la investigación de operaciones , la teoría de algoritmos y la teoría de la complejidad computacional . La optimización combinatoria consiste en encontrar el objeto óptimo en un conjunto finito de objetos [1] , lo cual es muy similar a la programación discreta . Algunas fuentes [2] entienden la programación discreta como programación entera , oponiéndola a la optimización combinatoria que trata con gráficos , matroidesy estructuras similares. Sin embargo, ambos términos están muy relacionados y, a menudo, se entrelazan en la literatura. La optimización combinatoria a menudo se reduce a determinar la asignación eficiente de los recursos utilizados para encontrar la solución óptima.
En muchos problemas de optimización combinatoria , la búsqueda exhaustiva no es realista. La optimización combinatoria incluye problemas de optimización en los que el conjunto de soluciones factibles es discreto o puede reducirse a un conjunto discreto.
La optimización combinatoria se utiliza para:
Sin embargo, la aplicación de la optimización combinatoria no se limita a estos ejemplos.
Existe una gran cantidad de literatura sobre algoritmos polinómicos de tiempo que funcionan en algunas clases de problemas de programación discreta, y una parte significativa de estos algoritmos pertenece a la teoría de la programación lineal . Algunos ejemplos de optimización combinatoria que caen en esta área son el problema de encontrar el camino más corto y el árbol de camino más corto , determinar el flujo máximo , encontrar árboles de expansión , encontrar correspondencias , problemas con matroides .
Los problemas de optimización combinatoria pueden verse como la búsqueda del mejor elemento en algún conjunto discreto, por lo que, en principio, se puede usar cualquier algoritmo de búsqueda o algoritmo metaheurístico . Sin embargo, los algoritmos generales de búsqueda no garantizan ni una solución óptima ni una solución rápida (en tiempo polinomial). Dado que algunos problemas de optimización discreta son NP-completos , como el problema del viajante de comercio, se espera lo mismo para otros problemas (si no es P=NP ).