La optimización combinatoria es una rama de la optimización matemática, pilar fundamental en la disciplina de la investigación operativa. Forma parte de la matemática discreta. Se caracteriza por la peculiar forma de construir el espacio de soluciones posibles. Concretamente, este espacio se construye mediante un proceso combinatorio de los elementos básicos que componen la estructura del problema. El cardinal de este conjunto de soluciones posibles crece de forma exponencial, de tal modo que, aún para un grupo reducido de elementos básicos del problema, la cardinalidad del conjunto de soluciones resulta intratable. Precisamente, en este modelo de crecimiento es donde reside la complejidad para hacer frente a este tipo de problemas ya que, en muchas ocasiones, la enumeración de todas las soluciones posibles y su análisis es el primer método para resolverlos.
La optimización combinatoria permite formular y resolver un gran número de problemas en ámbitos muy variados y actuales: planificación y gestión de operaciones, informática, logística, telecomunicaciones, marketing, etc.
Sin duda alguna, este tipo de problemas hace las delicias de los investigadores operativos ya que “contiene los dos elementos que hacen atractivo un problema a los matemáticos: planteamiento sencillo y dificultad de resolución” (Robert S. Garfinkel, 1985).”
Historia
Problemas de optimización combinatoria han existido siempre. En cualquier situación en la que que distribuir algunos elementos, o aquellas otras en las que es necesario analizar distintas ordenaciones de un conjunto finito de elementos, surge la necesidad de hacer frente a un problema de lo que hoy llamamos optimización combinatoria.
Desde un punto de vista riguroso y coherente, como corresponde al mundo de las matemáticas, la optimización combinatoria tiene una corta historia. Sin embargo, a lo largo del tiempo, sí es posible encontrar diferentes líneas de investigación que, de forma separada, han tratado problemas encuadrados en esta disciplina. Es a partir de la década de los 50 del siglo pasado, cuando se puede hablar de la aparición de la optimización combinatoria en el ámbito de la investigación operativa, con sus formulaciones y métodos propios.
Entre los problemas más estudiados y versátiles de la disciplina se encuentra el denominado problema del viajante, conocido por sus siglas en inglés TSP (Travelling Salesman Problem). Algunos estudiosos relacionan la historia del TSP con la de la propia optimización combinatoria.
Los orígenes de este problema no son claros, aunque en la literatura es posible extraer algunas notas que pueden ayudar a situarlo.
Así, es posible encontrar un indicio bibliográfico en la Alemania de 1.832, concretamente en un libro titulado “ El vendedor ambulante: cómo debe ser y qué debe hacer para obtener comisiones y éxito en su negocio. Por un vendedor ambulante veterano ”. En este libro se puede decir que aparece esbozado lo que hoy denominaríamos el planteamiento de este problema. Además se ofrece una solución para un problema que implica la construcción de un itinerario que recorre 45 ciudades alemanas.
Aplicaciones de la optimización combinatoria
Las aplicaciones de la optimización combinatoria son múltiples y aparecen en una gran cantidad de ámbitos muy diversos. A continuación se proponen algunas de las más empleadas.
Problemas de rutas: El problema del viajante se encuadra en este tipo de aplicaciones. En su versión más simple, este problema tiene por objetivo el recorrer una serie de puntos de paso obligado una única vez, con un coste o longitud de la ruta mínimo.
Otros problemas de rutas consideran la extensión de algunas de las restricciones del TSP. Así, en el caso de considerar que un único vehículo no puede visitar todos los puntos y son necesarios varios de ellos, se genera un problema denominado Problema de Rutas de Vehículos, conocido por el acrónimo VRP, del inglés Vehicle Routing Problem.
EL VRP es una aplicación imprescindible en cualquier organización que precise del diseño de un conjunto de rutas: entregas y recogida de paquetería, retirada de residuos, diseño de planes de movilidad urbanos, etc.
Además, admite una gran cantidad de variantes: entrega y recogida simultáneas, transporte de mercancías perecederas, existencia de ventanas de tiempo, presencia de limitaciones del personal que realiza la ruta, etc. Esta característica permite modelar una gran variedad de situaciones reales.
Problema de recubrimiento: Este problema puede surgir en varios ámbitos. Supongamos que una empresa necesita contratar a un conjunto de empleados para hacer frente a un conjunto de tareas. Cada empleado puede hacer frentes a una o a varias de estas tareas y, como es lógico, en función de sus competencias, el sueldo que han de recibir es diferentes. El objetivo del problema es diseñar un plan de contratación de empleados de mínimo coste que garantice la realización de las tareas de la empresa.
.
Problema de Corte: Al igual que otros problemas de Optimización Combinatoria, el problema de corte es fácil de definir intuitivamente, sin embargo no es fácil de modelar formalmente y presenta un alto grado de dificultad. Esta dificultad lleva implícita gran complejidad computacional.
El problema de corte tiene por objetivo extraer un conjunto de piezas de medidas determinadas, a partir de una pieza de tamaño mayor. Además, se pretende conseguir este conjunto de piezas generando la menor cantidad de material de desecho de la pieza mayor
Problema de la mochila: El Problema de la Mochila es un problema simple de entender: hay una persona que tiene una mochila con una cierta capacidad y tiene que elegir que elementos ubicará en ella. Cada uno de los elementos tiene un peso y aporta un beneficio. El objetivo de la persona es elegir los elementos que le permitan maximizar el beneficio sin excederse de la capacidad permitida.
A pesar de lo sencillo de su planteamiento, sus aplicaciones son múltiples. Por ejemplo, determinar la carga de un conjunto de contenedores, selección de proyectos, asignación de procesadores en sistemas en paralelo, etc.
Problema de localización: El objetivo de este tipo de problemas es determinar la ubicación óptima de un conjunto de instalaciones. Puede plantearse un problema de este tipo cuando las instalaciones son deseadas por la población (centros hospitalarios, parques, etc.) y en aquellos otros casos en los que las instalaciones no cuentan con el beneplácito de los ciudadanos (plantas energéticas, vertederos, etc.). Igualmente, este tipo de problemas puede plantearse considerando un conjunto finito de emplazamientos o considerar una área en la que establecer las instalaciones.
Metodología
Como regla general, los problemas de optimización combinatoria admiten formulaciones como problemas de programación matemática. Generalmente de tipo entero y, en particular, con variables de tipo binario. No obstante, en problemas que no sean de pequeña dimensión, se produce la denominada «explosión combinatoria», aumentando de forma muy notable el número de variables y restricciones. Este nivel de complejidad hace necesario que, en muchas ocasiones, los procedimientos exactos de resolución resultan ineficaces.
Este problema hace necesario el empleo de procedimientos heurísticos que permiten encontrar soluciones no óptimas, en un tiempo razonable. Estas soluciones se aproximan a los valores óptimos con cierta probabilidad. En futuras entradas se tratará esta cuestión de la complejidad algorítmica, y se podrá ampliar este aspecto. También es de destacar que en múltiples ocasiones aparecen problemas que combinan varios de estos modelos.
Conclusión
La optimización combinatoria es una rama de la optimización matemática. Presta atención a aquellos problemas que surgen en un contexto discreto. Los primeros problemas que se plantearon a lo largo de la historia se resolvieron por medio de «fuerza bruta», es decir, mediante la enumeración exhaustiva del espacio de soluciones, analizando los elementos de este conjunto y determinando aquella que proporcionaba el resultado óptimo.
Conforme este método se fue aplicando a problemas de mayor dimensión, quedó patente las limitaciones del mismo, ya que la cardinalidad de este conjunto de soluciones crece de forma exponencial. Por ello, los investigadores operativos que se enfrentan a este tipo de problemas han de conjugar de forma equilibrada, procedimientos exactos con heurísticos, tratando de encontrar la solución óptima o aproximarse a ella cuando esto no es posible.
Por último, cabe reseñar que bajo este epígrafe de optimización combinatoria aparece una gran cantidad de modelos diferentes, que permiten hacer frente a multitud de situaciones diversas en ámbitos muy distintos. En el apartado aplicaciones de esta entrada se ha querido dejar constancia de este hecho.
