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

...