Optimización combinatoria

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 de algoritmos 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 $(X,P,Y,f,\mathrm {extr} )$ 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
• Tabu search
• Algoritmos genéticos
• Optimización basada en colonias de hormigas
• Reactive search

Véase también

• Optimización discreta
• Algoritmos de búsqueda
• Evolución diferencial

Referencias

• William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 047155894X.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, A Compendium of NP Optimization Problems.
• Christos H. Papadimitriou, and Kenneth Steiglitz; Combinatorial Optimization: Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0486402584.

• Datos: Q1333872
• Multimedia: Combinatorial optimization / Q1333872