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 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 $(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).

Definición de problema de optimización

Un problema de optimización combinatoria se define como aquel en el que el conjunto de soluciones posibles es discreto. En otras palabras, se trata de un problema de optimización que involucra una cantidad finita o numerable de soluciones posibles.

Este tipo de problemas se diferencia de los problemas de optimización continuos, en los cuales el conjunto de soluciones posibles es infinito e incontable. Esta rama de la optimización se relaciona estrechamente con la investigación operativa, la teoría algorítmica y la teoría de la complejidad computacional. Los algoritmos de optimización combinatoria resuelven problemas que, en general, se consideran difíciles al explorar el amplio espacio de soluciones del problema en cuestión. Los buenos algoritmos de optimización combinatoria logran reducir el tamaño efectivo del espacio de búsqueda y explorarlo de manera eficiente.

Aquí entran los algoritmos de optimización combinatoria. Éstos son capaces de resolver problemas que suelen ser considerados difíciles, ya que exploran un amplio espacio de soluciones. Para lograrlo, estos algoritmos reducen efectivamente el tamaño del espacio y lo exploran de manera eficiente.

En el campo de la optimización combinatoria, es común que la mayoría de los procesos de resolución de problemas no puedan garantizar la solución óptima, incluso dentro del contexto del modelo que se esté utilizando. Sin embargo, la aproximación al óptimo suele ser suficiente para resolver los problemas en la práctica.

Existen diferentes métodos de resolución que pueden ser clasificados en cuatro grandes grupos:

1. Algoritmos constructivos, que construyen la solución a partir de una solución incompleta y utilizando los datos del problema y el conocimiento previo.
2. Algoritmos de mejora, que comienzan con una solución factible y completa y la modifican gradualmente de manera progresiva.
3. Estrategias de "divide y vencerás", que dividen el problema en fragmentos y aplican cualquier otra estrategia para resolver cada fragmento, y finalmente recomponen la solución.
4. Estrategias de aprendizaje, que toman decisiones en función de datos conocidos por el resultado de resoluciones anteriores o en la misma resolución.

Los métodos más comunes utilizados para resolver problemas en optimización combinatoria son heurísticos o metaheurísticos. Estos métodos son capaces de generar soluciones para el problema, aunque sean aproximaciones que no necesariamente alcancen la solución óptima.

En los primeros días de la Investigación Operativa, las limitaciones de cálculo automático llevaron a la creación de procedimientos heurísticos que pudieran encontrar soluciones de manera rápida, aunque no necesariamente las mejores.

Aunque los métodos heurísticos de resolución no pueden garantizar la solución óptima, son fundamentales por varias razones. En primer lugar, son capaces de generar soluciones, lo cual es mejor que no tener ninguna solución. En segundo lugar, obtener la solución óptima para un modelo que no representa exactamente el problema real no es necesariamente esencial. Por último, diseñar una buena heurística exige un conocimiento profundo del problema, lo cual puede conducir a mejoras de otro tipo.

Por lo tanto, los métodos heurísticos, incluyendo los procesos de mejora local y los algoritmos metaheurísticos, son herramientas valiosas para resolver problemas de optimización combinatoria en la práctica.

Ejemplos de problemas de optimización

Según su aplicación

1. Secuenciación: Referido al orden en el que un conjunto de trabajos deben pasar por una máquina. Este enfoque permite considerar aspectos como la duración de cada trabajo, la fecha de entrega, etc. El objetivo es encontrar el orden óptimo que permita cumplir con los objetivos del proyecto o la producción, minimizando la duración total o maximizando la eficiencia. Esto es posible mediante el uso de máquinas que trabajen en paralelo/serie.
2. Rutas: Los problemas de rutas están diseñados para establecer la mejor secuencia de recorrido para brindar un determinado servicio. Uno de los problemas clásicos en esta categoría es el problema del viajante de comercio (TSP), que implica visitar una vez y sólo una vez un conjunto de puntos. A este problema se le pueden añadir diversas variantes, como incluir varios viajantes, limitar la capacidad de los camiones o la disponibilidad de tiempo, incorporar ventanas temporales de entrega o recepción, entre otros. La complejidad de estos problemas aumenta a medida que se agregan más restricciones, pero su resolución eficiente puede generar importantes beneficios en términos de costos y eficiencia.

Según su clasificación formal

En esta categoría se encuentran problemas como:

1. El problema de la mochila (uni o multidimensional).
2. De máximo (o mínimo) flujo.
3. Problemas de Asignación Cuadrática.
4. Graph Partitioning Problem.
5. De camino más corto (o más largo).
6. El problema del vendedor viajero.
7. Programación lineal.
8. 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

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

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