Resumen Técnico: Un Algoritmo de Ramificación-Precio-y-Corte Numéricamente Seguro para el Problema de Partición de Ciclos con Restricción de Longitud

1. Definición del Problema

El Problema de Partición de Ciclos con Restricción de Longitud (LCCP, por sus siglas en inglés) es un problema de optimización de grafos definido sobre un grafo no dirigido $G=(V, E)$. El objetivo es particionar el conjunto de nodos $V$ en el número mínimo de ciclos disjuntos de tal manera que cada nodo $i$ sea cubierto exactamente una vez.

Cada nodo $i$ está asociado con un tiempo crítico $q_i > 0$, y cada arista $\{i, j\}$ tiene un tiempo de viaje $t_{i,j} \ge 0$. Un ciclo $C$ es factible en longitud si su tiempo total de viaje no excede el tiempo crítico de cualquier nodo contenido en él:
$$t(C) := \sum_{\{i,j\} \in C} t_{i,j} \le \min_{i \in C} \{q_i\}$$
El problema es conocido por ser NP-duro (reducible desde el Problema del Viajante) y no admite un algoritmo de aproximación en tiempo polinomial. Los enfoques anteriores de vanguardia utilizaron formulaciones compactas de Programación Entera Mixta (MIP) (basadas en Miller-Tucker-Zemlin o Restricciones de Eliminación de Subtours) que podían resolver instancias de hasta 52 nodos.

2. Metodología

Los autores proponen un algoritmo exacto de Ramificación-Precio-y-Corte (BPC) basado en una formulación de Partición de Conjuntos (SP).

2.1 Formulación de Partición de Conjuntos

En lugar de formulaciones compactas, el problema se modela como un problema de partición de conjuntos donde las variables representan ciclos completos factibles en longitud. La formulación minimiza $\sum_{C \in \Omega} \lambda_C$ sujeto a restricciones de cobertura $\sum_{C \in \Omega} a^C_i \lambda_C = 1$ para todo $i \in V$. Debido al tamaño exponencial de $\Omega$, los autores emplean Generación de Columnas para resolver la relajación de Programación Lineal (LP) de forma dinámica.

2.2 El Problema de Precios (LCPCCP)

La tarea computacional central es el Problema de Ciclo de Recolección de Premios con Restricción de Longitud (LCPCCP), que busca un ciclo con costo reducido negativo. Este problema es fuertemente NP-duro. Los autores lo resuelven utilizando:

• Programación Dinámica (DP): Un algoritmo de establecimiento de etiquetas donde las etiquetas rastrean los nodos visitados, el costo reducido, el tiempo total de viaje y el tiempo crítico mínimo del camino.
• Búsqueda Bidireccional: Explotando la naturaleza no dirigida del grafo, el algoritmo extiende las etiquetas desde un nodo inicial $s$ solo hasta que $t(\ell) < q(\ell)/2$. Las etiquetas no dominadas de las búsquedas hacia adelante y hacia atrás se combinan luego para formar ciclos completos. Esto reduce significativamente el espacio de búsqueda en comparación con la búsqueda monodireccional.
• Reglas de Dominancia: Las etiquetas se podan si otra etiqueta en el mismo nodo tiene un costo reducido menor o igual, un tiempo de viaje menor o igual y un subconjunto de nodos visitados.
• Relajación ng: Para manejar ciclos no elementales (revisitar nodos), los autores utilizan una relajación de camino ng con expansión de vecindad dinámica. Esto proporciona cotas inferiores válidas evitando la complejidad de imponer la elementalidad estrictamente durante las fases iniciales de búsqueda.
• Heurística Voraz (Greedy): Se ejecuta primero una heurística rápida para encontrar ciclos de mejora eliminando nodos duales negativos o insertando nodos duales positivos, reduciendo la necesidad de iteraciones costosas de DP.

2.3 Explotación de la Estructura

• Desigualdad Triangular: Para los nodos donde la desigualdad triangular se cumple localmente, los autores cambian a restricciones de cobertura de conjuntos. Esto restringe las variables duales a ser no negativas, permitiendo la eliminación de nodos con dual cero y habilitando la poda preventiva.
• Ruptura de Simetría: Para evitar generar el mismo ciclo desde diferentes nodos de inicio, la búsqueda se restringe para visitar solo nodos con tiempos críticos mayores o iguales al tiempo crítico del nodo de inicio (con desempate por índice).

2.4 Planos de Corte

El algoritmo integra dos familias de cortes:

• Cortes de Fila de Subconjuntos (SRCs): Aplicados a subconjuntos de nodos para limitar el número de ciclos que los cubren.
• Cortes de Clique (CCs): Basados en el grafo de conflicto de los ciclos.
  Los autores investigan el respeto de estos cortes dentro del problema de precios. Encuentran que, mientras los cortes de Clique se ignoran en el precio para evitar la complejidad, los cortes de Fila de Subconjuntos son respetados mediante la adición de recursos a las etiquetas, lo que mejora la convergencia en instancias difíciles específicas.

2.5 Seguridad Numérica

Una contribución clave es la implementación de límites numéricamente seguros. La aritmética de punto flotante puede conducir a soluciones duales infactibles debido a errores de redondeo. Los autores proponen un mecanismo de reparación dual:

1. Escalar los duales de punto flotante a enteros grandes.
2. Verificar la factibilidad dual de forma exacta usando aritmética entera.
3. Si es infactible, reducir el factor de escala e intentar de nuevo.
   Esto asegura que las cotas inferiores utilizadas para la ramificación sean matemáticamente rigurosas, evitando que el algoritmo afirme la optimalidad basada en artefactos numéricos.

2.6 Ramificación y Heurísticas

• Ramificación: Utiliza principalmente la Ramificación de Aristas (fijar las aristas para que estén o no en la solución). Se probó la ramificación de Ryan-Foster (sobre pares de nodos), pero se encontró que era menos robusta para esta estructura de problema específica.
• Heurísticas: Una variante de rama-y-precio heurística relaja las reglas de dominancia para encontrar soluciones primales de alta calidad rápidamente, las cuales se utilizan luego como arranques en caliente (warm starts) para el resolvedor exacto.

3. Principales Contribuciones

1. Formulación de Partición de Conjuntos: Demuestra que un enfoque basado en SP produce relajaciones LP significativamente más ajustadas (brecha promedio de la raíz de 0.4%) en comparación con las formulaciones compactas previas (brecha del 30.3%).
2. Precios por DP Bidireccional: Introduce una búsqueda bidireccional eficiente para el problema de precios LCPCCP, aprovechando la simetría de los grafos no dirigidos para reducir el espacio de búsqueda.
3. Seguridad Numérica: Proporciona un marco para obtener cotas inferiores demostrablemente correctas en un entorno de rama-y-precio combinando resolvedores de punto flotante con verificación de duales mediante aritmética entera exacta.
4. Integración Algorítmica: Combina el precio voraz, la relajación ng, la ruptura de simetría y la gestión específica de cortes en un resolvedor cohesivo.

4. Resultados Computacionales

El algoritmo fue probado en 84 instancias de referencia (14 a 100 nodos) contra el método anterior de vanguardia de rama-y-corte (bnc-sec).

• Rendimiento: El algoritmo de Ramificación-Precio-y-Corte propuesto (específicamente la configuración withsrc+pricing) resolvió 52 instancias con optimalidad probada, en comparación con las 40 del método anterior más avanzado.
• Escala: Resolvió con éxito instancias de hasta 76 nodos, cerrando 14 instancias previamente no resueltas. El límite anterior era de 52 nodos.
• Velocidad: El núcleo de rama-y-precio es, en promedio, 14.7 veces más rápido que el enfoque anterior más avanzado.
• Eficiencia del Nodo Raíz: 49 de las 52 instancias resueltas se resolvieron en el nodo raíz sin necesidad de ramificación, lo que destaca la fuerza de la relajación LP.
• Sobrecarga de Seguridad Numérica: La versión numéricamente segura resolvió el mismo número de instancias que la versión no segura, pero fue aproximadamente un 40% más lenta (media geométrica de 7.6s vs 4.5s). Sin embargo, no se detectaron resultados incorrectos en la versión no segura, y la sobrecarga se considera moderada dado que garantiza la corrección.

5. Significado y Reivindicaciones

El artículo afirma que la formulación de partición de conjuntos es el principal motor del rendimiento, proporcionando cotas ajustadas que permiten resolver la mayoría de las instancias en el nodo raíz. La búsqueda bidireccional y la ruptura de simetría se identifican como los componentes algorítmicos más impactantes para reducir el tiempo de ejecución.

Los autores señalan modestamente que, aunque el método mejora significamente el estado del arte, las instancias de más de 76 nodos siguen sin resolverse, y la rutina de precios sigue siendo el cuello de botella computacional. Sugieren que las mejoras futuras podrían requerir cotas duales más fuertes o algoritmos de precios más escalables (por ejemplo, aceleración por GPU). El trabajo establece un nuevo estándar para resolver LCCP, demostrando que los métodos exactos pueden manejar instancias más grandes y complejas cuando se combinan con técnicas de explotación de estructura y seguridad numérica.