Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search

Resumen Técnico: Características Geométricas de los Subproblemas en la Búsqueda de Vecindad Amplia Asistida por Máquinas de Ising

Planteamiento del Problema
Los problemas de optimización combinatoria con restricciones a gran escala, como el Problema de Enrutamiento de Vehículos (VRP), a menudo requieren formulaciones de Optimización Binaria No Restringida Cuadrática (QUBO) que exceden los límites de tamaño de entrada de las máquinas de Ising actuales o que sufren una degradación en la calidad de la solución a medida que aumenta el número de variables binarias. Aunque la Búsqueda de Vecindad Amplia (LNS) mitiga esto optimizando secuencialmente subproblemas restringidos, los enfoques existentes tratan principalmente el número de variables binarias como el único parámetro de control. Los autores postulan que el número de variables por sí solo es insuficiente para caracterizar un subproblema; diferentes reglas de construcción pueden generar estructuras internas, relaciones de restricciones y distribuciones geométricas distintas, incluso cuando los recuentos de variables son idénticos. La cuestión central es si la regla de construcción del subproblema afecta el proceso de optimización secuencial cuando el tamaño del subproblema (número de variables binarias) se mantiene fijo.

Metodología
El estudio investiga esta cuestión utilizando el VRP como banco de pruebas, comparando dos reglas distintas de construcción de subproblemas dentro de un marco de LNS asistido por máquinas de Ising:

1. LNS-K (Basado en la Estructura de Rutas): Este método construye subproblemas basados en las unidades semánticas del VRP. Selecciona un subconjunto de vehículos ($K'$) de la solución actual e incluye todos los clientes visitados por esos vehículos. Las variables del subproblema corresponden a las rutas de los vehículos seleccionados y sus clientes asociados.
2. LNS-Q (Basado en Variables QUBO): Este método construye subproblemas basados en la representación QUBO. Selecciona un subconjunto de variables binarias activas ($n'$) de la solución actual como "anclas" e incluye todas las variables involucradas en las restricciones asociadas con estas anclas. Este enfoque opera a nivel de representación en lugar de a nivel de dominio del problema.

Los autores utilizaron dos máquinas de Ising: la D-Wave Advantage 4.1 (recocido cuántico) para instancias de pequeña escala ($N=5, 6, 7$) y la Fixstars Amplify AE (basada en GPU) para instancias de gran escala ($N=100, 200, 300, 400$).

El protocolo experimental involucró dos comparaciones principales:

• LNS vs. Enfoque Naive: Comparación de la LNS secuencial frente a una entrega de un solo paso (single-shot) del QUBO completo, igualando el tiempo total de recocido.
• LNS-K vs. LNS-Q: Una comparación de "tamaño igualado" donde los parámetros $K'$ y $n'$ se ajustaron para que ambos métodos generaran subproblemas con exactamente el mismo número de variables binarias.

Las métricas clave incluyeron la distancia total de la solución, la trayectoria de mejora iterativa y la varianza de posición del conjunto de clientes seleccionados (una medida de la dispersión espacial de los clientes incluidos en el subproblema).

Resultados Clave

1. Eficacia de la Optimización Secuencial: Bajo presupuestos de tiempo de recocido total igualados, la LNS superó consistentemente al enfoque naive (QUBO completo de un solo paso) en ambas plataformas de hardware y tamaños de problema. La LNS mantuvo soluciones factibles durante todo el proceso y logró distancias totales significativamente más cortas, particularmente para instancias grandes ($N=400$).
2. Impacto de las Reglas de Construcción: Incluso cuando el número de variables binarias en los subproblemas se igualó estrictamente, LNS-K y LNS-Q exhibieron comportamientos de optimización diferentes.
   • Calidad de la Solución Final: LNS-K logró distancias totales finales más cortas que LNS-Q a través de los rangos de parámetros probados para la instancia de 400 clientes.
   • Trayectorias Iterativas: LNS-K demostró una mejora iterativa más rápida, particularmente para tamaños de subproblema igualados más pequeños ($K'=2, 3$).
3. Evolución Geométrica: Un hallazgo crítico concierne a la distribución espacial de los clientes seleccionados.
   • En LNS-K, la varianza de posición del conjunto de clientes seleccionados disminuyó significativamente durante las iteraciones, lo que indica que el algoritmo se enfocó progresivamente en clústeres de clientes más localizados espacialmente a medida que la solución mejoraba.
   • En LNS-Q, la varianza de posición se mantuvo casi constante durante las iteraciones, independientemente del tamaño del subproblema.

Significancia y Reivindicaciones
El artículo sostiene que el número de variables binarias es un descriptor insuficiente para los subproblemas en la optimización secuencial asistida por máquinas de Ising. El estudio demuestra que la regla de construcción en sí misma —específicamente, si las variables se agrupan por unidades semánticas del dominio del problema (rutas) o por relaciones de restricciones QUBO— moldea fundamentalmente la trayectoria de optimización y la calidad de la solución final.

Los autores argumentan que el diseño de subproblemas debe considerar no solo el tamaño, sino también la estructura semántica y geométrica heredada de la solución actual. El desempeño superior de LNS-K sugiere que preservar la estructura de rutas de la solución actual permite al algoritmo explotar la localidad espacial, conduciendo a reordenamientos locales más efectivos.

Limitaciones y Alcance
Los autores señalan explícitamente algunas limitaciones:

• Las conclusiones son específicas para las instancias de VRP probadas y la formulación QUBO particular utilizada.
• El análisis geomético es descriptivo; el artículo no establece un vínculo causal entre la disminución de la varianza de posición y la mejora en la distancia total, ni afirma que la localización espacial sea la única causa del éxito de LLNS-K.
• La comparación detallada de la estructura se realizó principalmente en la plataforma Fixstars Amplify AE; no se afirma que los resultados sean independientes del hardware.
• El estudio no proporciona un benchmark exhaustivo contra las heurísticas clásicas de estado del arte para el enrutamiento de vehículos, centrándose en cambio en la mecánica interna de la LNS asistida por máquinas de Ising.

En conclusión, el artículo postula que el diseño de subproblemas efectivos para máquinas de Ising requiere integrar la información estructural de la solución actual, yendo más allá de las simples restricciones de conteo de variables.