PDF de programación - Estudio de técnicas de búsqueda por vecindad a muy gran escala

Estudio de técnicas de búsqueda por vecindad a muy gran escala

Ravindra K. Ahuja

Departamento de ingeniería industrial y de sistemas

Universidad de Florida

Gainesville, FL 32611, USA

[email protected]

Özlem Ergun

Centro de investigación operativa

Instituto tecnológico de Massachussets

Cambridge, MA 02139, USA

[email protected]

James B. Orlin

Escuela Sloan de dirección

Instituto tecnológico de Massachussets

Cambridge, MA 02139, USA

[email protected]

Departamento de matemáticas, estadística y ciencias informáticas

Abraham P. Punnen

Universidad de New Brunswick

Saint John, New Brunswick, Canada E2L 4L5

[email protected]

(22 de julio de 1999)

(Revisado el 11 de octubre de 2000)



1

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



2

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



3

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 linea