Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

Resumen Técnico: Búsqueda de Vecindad Amplia Asistida por Máquinas de Ising con Tamaño de Subproblema Ajustable de Forma Flexible

Planteamiento del Problema
Las máquinas de Ising sirven como resolvedores heurísticos para la optimización combinatoria mediante la búsqueda de estados de baja energía en modelos de Ising o de Optimización Binaria Cuadrática sin Restricciones (QUBO). Sin embargo, aplicar estas máquinas directamente a problemas restringidos de gran escala (el "método ingenuo") enfrenta dos dificultades primordiales:

1. Escalabilidad: El número de variables binarias en la formulación QUBO a menudo excede la capacidad de hardware de las máquinas de Ising actuales.
2. Factibilidad: Las restricciones se incorporan típicamente como términos de penalización. En consecuencia, el espacio de búsqueda incluye soluciones infactibles, y los estados de baja energía no necesariamente corresponden a soluciones factibles de alta calidad del problema original.

Los enfoques existentes, como el fijado de variables o el divide y vencerás, intentan reducir el tamaño del problema, pero a menudo tienen dificultades para equilibrar el tamaño del subproblema con la capacidad de reconstruir soluciones factibles para el problema original. La Búsqueda de Vecindad Amplia (LNS, por sus siglas en inglés) ofrece un marco donde una solución factible actual se mejora iterativamente reoptimizando un subproblema (una "vecindad"). Mientras que la LNS preserva la factibilidad si el método de generación del subproblema está diseñado correctamente, el rendimiento de la LNS asistida por máquinas de Ising es altamente sensible al tamaño del subproblema. Si el subproblema es demasiado pequeño, la mejora potencial por iteración es limitada; si es demasiado grande, la calidad de la solución de la máquina de Ising se degrada debido a la expansión del espacio de búsqueda.

Metodología
El artículo se centra en dos problemas: el Problema de Rutas de Vehículos (VRP) y el Probleza de Mochilas Múltiples Cuadráticas (QMKP).

• Método Existente (LNS-V): Para el VRP, los autores analizan un método previo (LNS-V) que selecciona un subconjunto de vehículos y reoptimiza sus rutas completas. Aunque esto preserva la factibilidad, el tamaño del subproblema se controla únicamente mediante el número de vehículos seleccionados ($V'$). Debido a que se reoptimiza la ruta completa de un vehículo seleccionado, el número de variables escala como $(V')^2(T-2)^2$ (donde $T$ es el número total de pasos). Esto resulta en una granularidad gruesa; cambiar $V'$ en uno puede causar un salto masivo en el recuento de variables, lo que dificulta ajustar el tamaño del subproblema al rango óptimo para la máquina de Ising.

• Método Propuesto (LNS-VT): Para abordar el problema de la granularidad, los autores proponen LNS-VT. Además de seleccionar $V'$ vehículos, LNS-VT introduce un nuevo parámetro: el número de pasos consecutivos ($T'$) a reoptimizar para cada vehículo seleccionado.

  • Mecanismo: Para cada vehículo seleccionado, se extrae un segmento contiguo de la ruta (de longitud $T_{seg} = \min(T', \text{pasos válidos reales})$). El subproblema reoptimiza la asignación y el orden de los sitios dentro de estos segmentos específicos mientras mantiene el resto de la ruta fijo.
  • Factibilidad: Al fijar los sitios fuera de los intervalos de extracción y asegurar que los segmentos extraídos solo involucren sitios que no sean depósitos, el método garantiza que la reinserción de cualquier solución factible del subproblema resulte en una solución factible para el VRP original.
  • Control de Variables: El número de variables libres en LNS-VT es aproximadamente $(V'T')^2$. Esto permite un control de grano fino sobre el tamaño del subproblema de forma independiente de los pasos totales $T$ del problema.

• Extensión a QMKP: Los autores aplican el mismo principio de diseño al QMKP. Construyen un método de generación de subproblemas que selecciona un subconjunto de mochilas ($K'$) y un subconjunto de artículos ($N'$) para reoptimizar. Este método también preserva la factibilidad al fijar los artículos que no están en el conjunto seleccionado y ajustar las restricciones de capacidad para la capacidad residual de las mochilas seleccionadas.

Resultados Clave
Se realizaron experimentos numéricos utilizando un VRP de 300 sitios y 5 vehículos, y un QMKP de 200 artículos y 5 mochilas, utilizando la máquina de Ising Fixstars Amplify AE.

• Rendimiento del VRP:

  • LNS-VT superó tanto al método ingenuo como al LNS-V existente.
  • La mejor configuración de LNS-VT (específicamente $V'=2, T'=40$) redujo el valor objetivo en aproximadamente un 10% en relación con LNS-V tras 100 iteraciones.
  • LNS-VT alcanzó la calidad de solución final de L_NS-V utilizando solo alrededor del 30% de las iteraciones.
  • Sensibilidad de las Variables: Se encontró que el tamaño óptimo del subproblema (en términos de variables de asignación de sitios que no son depósitos) se encontraba entre 6,000 y 10,000. El LNS-V existente no pudo alcanzar este rango con $V' \ge 2$ (su mínimo era de ~14,400 variables), lo que explica su rendimiento inferior.
  • Necesidades Dinámicas: El tamaño apropiado del subproblema cambió durante el proceso de búsqueda. Los subproblemas más grandes fueron más efectivos en las iteraciones iniciales (valores de objetivo altos), mientras que los subproblemas más pequeños fueron más efectivos en las iteraciones finales (refinamiento de soluciones de alta calidad).

• Rendimiento del QMKP:

  • La LNS aplicada al QMKP también superó al método ingenuo.
  • Se encontró que el tamaño óptimo del subproblema para QMKP era significativamente menor, aproximadamente de 100 a 150 variables.
  • Esta diferencia tan marcada con respecto al VRP (6,000–10,000) indica que el tamaño óptimo del subproblema depende de la clase de problema específica y de la formulación QUBO, no solo de las capacidades de la máquina de Ising.

Significado y Reivindicaciones
El artículo sostiene que para que la LNS asistida por máquinas de Ising sea efectiva en problemas restringidos de gran escala, la preservación de la factibilidad por sí sola es insuficiente. La capacidad de ajustar flexiblemente el tamaño del subproblema para que coincida con el punto óptimo de rendimiento de la máquina de Ising es un factor de diseño crítico.

El estudio demuestra que:

1. La introducción de un parámetro de control adicional (pasos consecutivos para VRP, o recuentos de artículos/mochilas para QMKP) permite un ajuste de grano fino del tamaño del subproblema, lo cual es imposible con métodos que solo varían el número de entidades seleccionadas.
2. Existe un rango óptimo de variables para el subproblema que maximiza la calidad de la solución, y este rango varía significativamente entre diferentes clases de problemas (VRP vs. QMKP).
3. El tamaño óptimo del subproblema también puede depender de la calidad de la solución actual, lo que sugiere que las configuraciones de parámetros estáticos pueden no ser óptimas durante todo el proceso de búsqueda.

Los autores concluyen que, si bien sus resultados son específicos para las instancias y la configuración de la máquina probadas, el principio de generación de subproblemas con conciencia de la estructura y ajustable de forma flexible es una dirección prometedora para la optimización combinatoria restringida. Señalan que el trabajo futuro debería centrarse en desarrollar estrategias adaptativas para seleccionar automáticamente los parámetros del subproblema basándose en la etapa de búsqueda y la estructura del problema.