Estudio De técnicas De búsqueda Por Vecindad A Muy Gran Escala

Ravindra K. Ahuja, Özlem Ergun, James B. Orlin, Abraham P. Punnen

Resumen

Muchos problemas de optimización de interés práctico resultan intratables mediante técnicas de cálculo. Ante esta dificultad, los algoritmos heurísticos (o de aproximación) se revelan como un medio útil para su resolución, ya que permiten obtener soluciones casi óptimas en un tiempo razonable. Los algoritmos de mejora son algoritmos heurísticos que, por lo general, parten de una solución factible y tratan de hallar, por medio de iteraciones, una solución aún mejor. Los algoritmos de búsqueda por vecindad (también llamados algoritmos de búsqueda local) constituyen un tipo bastante amplio de algoritmos de mejora en los que en cada iteración se obtiene una solución mejorada buscando en la "vecindad" de la solución existente. Un aspecto crítico del diseño de esta clase de algoritmos es la elección de la estructura de la vecindad; es decir, el modo en el que se va a definir ésta. Como regla general, cuanto más amplia sea la vecindad, mayor será tanto la calidad de las soluciones localmente óptimas como la precisión de la solución final que se obtenga. Pero, al mismo tiempo, cuanto más amplia sea la vecindad, más tiempo será necesario para realizar la búsqueda dentro de ella en cada iteración. Por esta razón, una vecindad muy amplia produce necesariamente una heurística más eficaz, a menos que la búsqueda se realice de un modo muy eficiente. El presente estudio se concentra en algoritmos de búsqueda local en los que el tamaño de la vecindad es “muy grande” con respecto al tamaño de los datos y en los que la búsqueda local se hace con criterios de máxima eficiencia. En él se analizan tres tipos muy amplios de algoritmos de búsqueda por vecindad a muy gran escala (VLSN: Very Large-Scale Neighborhood): (1) métodos de profundidad variable en los que la búsqueda local se realiza de modo heurístico, (2) aplicación de la programación dinámica o de técnicas de flujo de redes a vecindades amplias, y (3) vecindades grandes inducidas por restricciones del problema original que pueden resolverse en tiempo polinómico.

1. Introducción

Muchos problemas de optimización de interés práctico resultan intratables mediante técnicas de cálculo. Ante esta dificultad, los algoritmos heurísticos (o de aproximación) se revelan como un medio útil para su resolución, ya que permiten obtener soluciones casi óptimas en un tiempo razonable. Los trabajos dedicados a algoritmos heurísticos suelen dividir éstos en dos amplias categorías: algoritmos de construcción (o constructivos) y algoritmos de mejora. Los primeros montan una solución partiendo de cero, mediante la asignación de valores a una o varias variables de decisión al mismo tiempo, mientras que los algoritmos de mejora parten de una solución factible y tratan de hallar una mejor por medio de iteraciones. Los algoritmos de búsqueda por vecindad (también llamados algoritmos de búsqueda local) constituyen un tipo bastante amplio de algoritmos de mejora en los que en cada iteración se obtiene una solución mejorada buscando en la "vecindad" de la solución existente. El presente estudio se concentra en algoritmos de búsqueda local en los que el tamaño de la vecindad es “muy grande” con respecto al tamaño de los datos y en los que la búsqueda local se hace con criterios de máxima eficacia. En instancias grandes de problemas, la búsqueda de este tipo de vecindades de modo explícito resulta poco práctica, lo que hace necesario realizar la búsqueda en un segmento más pequeño de la vecindad o bien desarrollar algoritmos que resulten eficaces en búsquedas de modo implícito en la vecindad.

Un aspecto crítico del diseño de esta clase de algoritmos es la elección de la estructura de la vecindad (es decir, el modo en el que se va a definir ésta), ya que del tipo de estructura que se elija dependerá el que la búsqueda de vecindad desarrolle soluciones altamente precisas o soluciones con óptimos locales muy pobres. Como regla general, cuanto más amplia sea la vecindad, mayor será tanto la calidad de las soluciones localmente óptimas como la precisión de la solución final que se obtenga. Pero, al mismo tiempo, cuanto más amplia sea la vecindad, más tiempo será necesario para realizar la búsqueda dentro de ella en cada iteración. Dado que se suelen ejecutar varios algoritmos de búsqueda local con distintos puntos de partida, la mayor duración de los tiempos de ejecución para cada iteración requiere un menor número de ejecuciones por tiempo unitario. Por esta razón, una vecindad muy amplia produce necesariamente una heurística más eficaz, a menos que la búsqueda se realice de un modo muy eficiente.

Varios de los métodos más utilizados por su alta eficiencia en investigación operativa pueden entenderse como técnicas de búsqueda por vecindad a gran escala. Así, por ejemplo, si contemplamos el algoritmo simplex para la resolución de programas lineales como un algoritmo de búsqueda local, tendremos que la generación de columnas es a su vez un método de búsqueda por vecindad a gran escala, al igual que ocurre con las técnicas de extrapolación empleadas para la resolución de muchos problemas de flujo de redes. El algoritmo de cancelación del ciclo de coste negativo que se usa para resolver el problema del flujo de coste mínimo y el algoritmo del camino de aumento que resuelve problemas de ajuste son dos ejemplos de ello.

En el presente estudio, hemos clasificado los métodos de vecindad a gran escala en tres categorías que pueden coincidir parcialmente. La primera de ellas comprende los métodos de profundidad variable: una serie de algoritmos que se centran en vecindades exponencialmente grandes en las que realizan búsquedas parciales por medio de la heurística. La segunda categoría comprende algoritmos de mejora basados en flujos de red; métodos de búsqueda local que emplean técnicas de flujo de red para identificar posibilidades de mejora en la vecindad. Por último, en la tercera categoría se analizan vecindades para problemas NP-difíciles inducidos por subconjuntos de restricciones de los problemas que se pueden resolver en tiempo polinómico. Aunque hemos introducido el concepto de búsqueda por vecindad a gran escala al hacer referencia a técnicas de generación de columnas para programas lineales y a técnicas de extrapolación para flujos de redes, no se insiste sobre los programas lineales. Por el contrario, el estudio se concentra en la aplicación de técnicas de búsqueda por vecindad a gran escala a problemas de optimización NP-difíciles.

Esta monografía se halla estructurada del modo que a continuación se describe. En el apartado 2 se incluye una breve descripción general de la búsqueda local. El apartado 3 comprende un análisis de métodos de profundidad variable. El apartado 4 trata sobre algoritmos de búsqueda por vecindad a gran escala basados en técnicas de flujo de redes. En el apartado 5 se analizan técnicas eficientes para la resolución de supuestos especiales de problemas NP-difíciles de optimización combinatoria, así como de vecindades muy amplias basadas en ellos. El apartado 6 describe las mediciones de vecindades, que pueden servir de guía para el desarrollo de algoritmos de búsqueda local con respecto a una vecindad dada. Por último, en el apartado 7 se analiza el rendimiento computacional de varios de los algoritmos vistos en los apartados anteriores.

2. Búsqueda local: esquema general

Comenzaremos por introducir formalmente un problema de optimización combinatoria, junto con el concepto de vecindad. Existen diversas maneras de representar este tipo de problemas, todas ellas basadas en métodos de representación del conjunto de soluciones factibles. En este apartado, representaremos el conjunto de soluciones factibles como subconjuntos de un conjunto finito, formulándolo del siguiente modo:

Sea E = {1, 2,..., m} un conjunto finito. En general, la cardinalidad de un conjunto S se indica mediante |S|. Supongamos, además, que F ⊆ 2E, donde 2E indica el conjunto formado por todos los subconjuntos de E. Los elementos de F se denominan soluciones factibles. Sea f: F → ℜ, llamándose a la función f la función objetivo. Con estos datos, una instancia de un problema de optimización combinatoria (POC) se representará del siguiente modo:

Minimizar {f(S) : S ∈ F}.

Damos por hecho que la familia F no nos viene dada explícitamente mediante el listado de todos sus elementos; sino que se halla representada en una forma compacta de tamaño polinómico en m. El par (F, f) indica una instancia de un problema de optimización combinatoria. En la mayor parte de los problemas que veremos, la función de coste es una función lineal; es decir, existe un vector f1, f2,…, fm tal que, para todos los conjuntos factibles, S, f(S) = Σi∈Sfi.

Supongamos que (F, f) es una instancia de un problema de optimización combinatoria. La función de vecindad es un punto de definición del mapa N: F→ 2E. En esta función, cada valor de S ∈ F tiene asociado un subconjunto N(S) de E. El conjunto N(S) recibe el nombre de vecindad de la solución S, y podemos suponer, sin pérdida de generalidad, que S ∈ N(S). Se dice que una solución S* ∈ F es localmente óptima con respecto a una función de vecindad N cuando f(S*) ≤ f(S) para todo S ∈ N(S*). Asimismo, se dice que N(S) es exponencial cuando |N(S)| crece de manera exponencial en m a medida que el valor de esta última se incrementa. A lo largo de la mayor parte de este estudio, veremos vecindades de tamaño exponencial, además de vecindades cuyo tamaño es demasiado amplio para realizar en ellas búsquedas explícitas en la práctica. Así, por ejemplo, una

...