Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems

Resumen Técnico: Evaluación del Desempeño de las Formulaciones Directas de Orden Superior en Problemas de Optimización Combinatoria

Planteamiento del Problema
Los problemas de optimización combinatoria se encuentran frecuentemente en campos como la logística, el diseño de materiales y la optimización de carteras. Aunque muchos de estos problemas son NP-duros y requieren enfoques heurísticos, existe una barrera significativa en su implementación en "máquinas de Ising" (incluyendo el hardware de recocido cuántico y los resolvedores inspirados en la física). La mayoría de las plataformas de hardware existentes aceptan entradas exclusivamente en el formato de Optimización Binaria No Restringida Cuadrática (QUBO), lo que restringe las funciones objetivo a términos lineales y cuadráticos de variables binarias.

Sin embargo, numerosos problemas del mundo real, como el muestreo de polímeros, el plegamiento de proteínas y tareas específicas de rutas, involucran inherentemente interacciones de orden superior (cúbicas, cuarticas, etc.). Para resolver estos problemas en el hardware estándar, los investigadores deben aplicar técnicas de "reducción de orden" para transformar problemas de Optimización Binaria de Orden Polinómico (PUBO) a la forma QUBO. Este proceso introduce variables auxiliares y términos de penalización para mantener la consistencia lógica. Los autores postulan que esta transformación aumenta inevitablemente el tamaño del problema y la complejidad estructural, lo que potencialmente degrada la calidad y la estabilidad de la solución; no obstante, el impacto específico de manejar directamente los términos de orden superior frente a reducirlos no ha sido cuantificado exhaustivamente en una plataforma unificada para instancias prácticas a gran escala.

Metodología
Para abordar esta brecha, el estudio emplea un marco de evaluación comparativa utilizando el Fixstars Amplify Annealing Engine (Amplify AE). Este resolvedor de alto rendimiento, basado en el Recocido Simulado (SA) y paralelización masiva en GPU, ofrece dos modos distintos:

1. Resolvedor PUBO: Optimiza directamente funciones objetivo que contienen términos de hasta cuarto orden sin modificaciones.
2. Resolvedor QUBO: Resuelve los mismos problemas tras aplicar el método de sustitución para la reducción de orden. Este método reemplaza productos de variables binarias con nuevas variables auxiliares y aplica restricciones mediante términos de penalización (específicamente, $x_1x_2 = y_{1,2}$).

El estudio compara estos dos enfoques en dos problemas de referencia que contienen naturalmente términos de orden superior:

• Secuencia Binaria de Baja Autocorrelación (LABS): Un problema que busca secuencias binarias con energía de autocorrelación mínima. La función de energía involucra términos de autocorrelación al cuadrado, lo que resulta en interacciones de cuarto orden ($s_i s_{i+k} s_j s_{j+k}$).
• Problema de Rutas de Vehículos (VRP) con Equilibrio de Distancias: Un problema multiobjetivo que minimiza la distancia total de viaje mientras minimiza simultáneamente la varianza de las distancias entre vehículos. El término de varianza introduce interacciones de cuarto orden cuando se expande.

Los experimentos se realizaron con tiempos de computación fijos (60 segundos) a través de varios tamaños de problema. Para LABS, las longitudes de secuencia ($N$) oscilaron entre 5 y 99. Para VRP, se variaron el número de ubicaciones de clientes ($P$) y el número de vehículos ($V$). El resolvedor QUBO utilizó un coeficiente de penalización fijo ($p=1$) para el método de sustitución, mientras que el resolvedor PUBO no requirió tal parámetro de ajuste.

Contribuciones Clave y Resultados
El artículo proporciona un análisis cuantitativo de las compensaciones entre la formulación directa de PUBO y la formulación reducida de QUBO:

1. Calidad de la Solución y Estabilidad:

   • LABS: El resolvedor PUBO alcanzó consistentemente valores de energía normalizados más bajos (más cercanos a la solución óptima) con desviaciones estándar significativamente menores en comparación con el resolvedor QUBO. La brecha de rendimiento se amplió a medida que aumentaba la longitud de la secuencia $N$.
   • VRP: En el análisis de instancia única, el resolvedor PUO produjo compensaciones más estables entre la distancia total y la varianza de la distancia. Los diagramas de dispersión revelaron que las soluciones QUBO estaban ampliamente dispersas y no lograban alcanzar la región de la varianza mínima real, mientras que las soluciones PUBO se concentraron cerca de la frontera de Pareto.
   • Análisis de Hipervolumen: A través de 30 instancias de VRP generadas aleatoriamente, el resolvedor PUBO logró consistentemente indicadores de hipervolumen más grandes (una medida de la diversidad y calidad del conjunto de soluciones) que el resolvedor QUBO, confirmando su superioridad en la optimización multiobjetivo.

2. Expansión de Variables:

   • El estudio cuantificó la "explosión de variables" causada por la reducción de orden. Tanto para LABS como para VRP, el número de variables binarias en la formulación QUBO creció rápidamente con el tamaño del problema, alcanzando decenas de veces el número de variables en la formulación directa de PUBO para instancias grandes. Esta expansión amplía el espacio de búsqueda, contribuyendo a la degradación observada en la estabilidad de la solución.

3. Sensibilidad a los Coeficientes de Penalización:

   • Los autores investigaron la sensibilidad del enfoque QUBO al coeficiente de penalización ($p$) utilizado en el método de sustitución. Un análisis de mapa de calor para el problema LABS demostró que el coeficiente de penalización óptimo varía significadamente con el tamaño del problema ($N$). Ningún valor único de $p$ proporcionó un rendimiento consistente en todas las escalas, lo que resalta la dificultad de ajustar las formulaciones reducidas para aplicaciones generales.

Significancia y Reivindicaciones
El artículo sostiene que el manejo directo de los términos de orden superior mediante formulaciones PUBO ofrece ventajas distintivas sobre los métodos tradicionales de reducción de orden al resolver problemas de optimización combinatoria en hardware moderno de tipo Ising. La principal significancia radica en la demostración de que:

• Integridad Estructural: Preservar la estructura original del problema (PUBO) evita la expansión artificial del espacio de búsqueda causada por las variables auxiliares.
• Robustez: La formulación directa elimina la necesidad de ajustar los coeficientes de penalización, los cuales son sensibles a la escala del problema y pueden desestabilizar el proceso de búsqueda.
• Escalabilidad: El enfoque PUBO mantiene una calidad de solución y estabilidad superiores a medida que aumentan los tamaños de los problemas, mientras que el enfoque QUBO sufre los efectos compuestos de la expansión de variables y la aplicación de restricciones.

Los autores concluyen que, si bien la reducción de orden ha sido efectiva para diversos problemas, la formulación directa de PUBO representa un enfoque prometedor para escenarios de optimización a gran escala y prácticos, ofreciendo tanto simplicidad estructural como estabilidad computacional. El estudio sugiere que el desarrollo futuro de hardware y resolvedores debería continuar apoyando la ejecución directa de órdenes superiores para aprovechar plenamente estos beneficios en aplicaciones del mundo real.