Optimización combinatoria para niños
La optimización combinatoria es una rama de la optimización en matemáticas aplicadas y en ciencias de la computación, relacionada con la investigación de operaciones, Teoría algorítmica de la información y teoría de la complejidad computacional. También está relacionada con otros campos, como la inteligencia artificial e ingeniería de software. Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen ser difíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente.
Los algoritmos de optimización combinatoria a menudo son implementados en lenguajes imperativos como C y C++ entre otros softwares inteligentes en lenguajes de programación lógicos tales como Prolog, o incluso en lenguajes multi-paradigma tales como Oz.
Mediante el estudio de la teoría de la complejidad computacional es posible comprender la importancia de la optimización combinatoria. Los algoritmos de optimización combinatoria se relacionan comúnmente con problemas NP-hard. Dichos problemas en general no son resueltos eficientemente, sin embargo, varias aproximaciones de la teoría de la complejidad sugieren que ciertas instancias (ej. "pequeñas" instancias) de estos problemas pueden ser resueltas eficientemente. Dichas instancias a menudo tienen ramificaciones prácticas muy importantes.
Definición formal
Una instancia de un problema de optimización combinatoria puede ser descrito formalmente como una tupla 
donde
- X es el espacio de soluciones (en el cual f y P están definidos)
- P es la factibilidad predicado.
- Y es el conjunto de soluciones factibles.
- f es la función objetivo.
- extr es el extremo (normalmente min o max).
Ejemplo de problemas
- El problema del vendedor viajero.
- Programación lineal.
- El problema de las n-reinas.
Métodos
Los métodos de búsqueda heurísticos (algoritmos metaheuristicos) como los listados abajo han sido usados para resolver problemas de este tipo.
- Búsqueda local
- Simulated annealing
- GRASP
- Inteligencia de enjambre
- Búsqueda tabú
- Algoritmos genéticos
- Optimización basada en colonias de hormigas
- Reactive search
Véase también
En inglés: Combinatorial optimization Facts for Kids
- Optimización discreta
- Algoritmos de búsqueda
- Evolución diferencial
