Resumen Técnico: Sobre la Inferencia de Restricciones Cumulativas

Planteamiento del Problema

Las restricciones cumulativas son un pilar de la programación de restricciones (CP) para la planificación, modelando recursos renovables limitados. Sin embargo, las técnicas de propagación estándar suelen razonar sobre cada restricción de recurso de forma independiente. Este "punto de vista de recurso único" no logra capturar las interacciones entre múltiples recursos, lo que conduce a una degradación severa del rendimiento en benchmarks específicos (por ejemplo, la estructura del "problema 3n").

Intentos previos para abordar esto, como el enfoque "Unite and Lead" (UNL) de Sidorov et al. [2025a], identificaron con éxito estructuras disyuntivas ocultas (conjuntos de tareas que no pueden ejecutarse en paralelo). Sin embargo, UNL sufre dos limitaciones críticas:

1. Falta de Generalidad: Está restringido al razonamiento disyuntivo y no puede derivar interacciones de múltiples recursos más generales.
2. Sobrecarga de Búsqueda: Requiere la detección explícita de clics disyuntivos mediante sondeo (probing) durante la búsqueda, lo que incurre en una sobrecarga significativa que a menudo ralentiza los solvers en órdenes de magnitud en instancias que carecen de tales estructuras.

El problema central abordado en este artículo es cómo inferir interacciones válidas de múltiples recursos y fortalecer el modelo sin incurrir en las penalizaciones de tiempo de búsqueda asociadas con la detección dinámica de clics.

Metodología

El enfoque propuesto redefine las restricciones cumulativas como desigualdades lineales sobre vectores de ocupación y aplica técnicas de geometría poliédrica y programación entera mixta (MIP) para inferir nuevas restricciones en el nodo raíz (preprocesamiento).

1. Fundamento Teórico

El método se basa en la representación de los tiempos de inicio $s_i$ y las duraciones $d_i$ de las tareas como vectores de ocupación $\langle s_i | d_i \rangle$, donde el vector es 1 durante el intervalo $[s_i, s_i + d_i)$ y 0 de lo contrario. Una restricción cumulativa $\sum r_i \langle s_i | d_i \rangle \le C$ se visualiza así como una desigualdad lineal.

• El Lema 7 establece que cualquier desigualdad válida para el poliedro definido por los vectores de ocupación corresponde a una restricción cumulativa válida para el problema de planificación original.
• Esto permite que el problema de inferir restricciones sea tratado como la generación de planos de corte (cutting planes) válidos.

2. El Flujo de Trabajo Basado en Levantamiento (Lifting)

En lugar de buscar clics disyuntivos dinámicamente, el algoritmo realiza un paso de preprocesamiento estático que consta de tres etapas:

1. Descubrimiento de Coberturas (Cover Discovery): El algoritmo enumera "coberturas" (conjuntos de tareas $C$ donde la suma de los requerimientos de recursos excede la capacidad, es decir, $\sum_{i \in C} r_i > C$). Genera coberturas "cortas" (cardinalidad 2 y 3) y coberturas "largas" (agrupadas por valores de consumo de recursos) y selecciona los candidatos más prometedores basándose en una métrica de límite de capacidad ($L$), que estima la duración mínima (makespan) abarcada por las tareas.
2. Levantamiento (Lifting): Para cada cobertura descubierta, el método aplica el procedimiento de levantamiento (Padberg, 1975). Esto fortalece la desigualdad de cobertura básica ($\sum_{i \in C} x_i \le |C| - 1$) determinando el coeficiente máximo $\beta$ para las variables que originalmente no estaban en la cobertura, de tal manera que la desigualdad $\sum_{i \in C} x_i + \beta x_j \le |C| - 1$ siga siendo válida. Esto se logra resolviendo subproblemas auxiliares (maximizando el lado izquierdo de la desigualdad actual bajo restricciones específicas).
3. Inyección de Restricciones: Las desigualdades levantadas resultantes se convierten de nuevo en nuevas restricciones cumulativas y se inyectan en la instancia del problema antes de que el solver de CP comience su búsqueda.

La implementación utiliza Gurobi 12 para resolver los subproblemas de levantamiento y limita el número de restricciones generadas ($N_{out}$) y las coberturas iniciales ($N_{cover}$) para controlar el tiempo de preprocesamiento.

Contribuciones Clave

• Marco Algorítmico: Un nuevo método para inferir restricciones cumulativas que generaliza más allá del razonamiento disyuntivo, capturando interacciones de múltiples recursos a través de desigualdades válidas.
• Estrategia de Preprocesamiento: Un enfoque de nodo raíz que evita la sobrecarga de tiempo de búsqueda de la detección dinámica de clics, eliminando así la inestabilidad observada en los métodos anteriores basados en UNL.
• Integración de Técnicas de MIP: La aplicación de levantamiento e desigualdades de cobertura de la programación entera al dominio de la planificación de programación de restricciones.
• Métrica de Calidad: La introducción del ratio de límite de capacidad como una heurística para seleccionar qué coberturas levantar y qué restricciones inferidas retener.

Resultados Experimentales

El método fue evaluado en benchmarks estándar de RCPSP (736 instancias) y RCPSP/max (349 instancias) utilizando solvers de vanguardia (Pumpkin y CP-SAT).

• Ganancias de Rendimiento:
  • Optimalidad: Para las instancias resueltas a la optimalidad, el levantamiento redujo significativamente el tiempo de resolución, a veces de decenas de minutos a menos de un segundo.
  • Progreso de la Búsqueda: En instancias no resueltas a la optimalidad, el enfoque mejoró sustancialmente el integral dual (tasa de mejora del límite inferior), indicando una convergencia más rápida hacia límites ajustados.
  • Estabilidad: A diferencia de UNL, la degradación del rendimiento (aumento del tiempo de resolución) fue poco común. Solo 19 pares de ejecuciones mostraron ralentizaciones significativas, e incluso el evento de "degradación de 2x" ocurrió solo en el percentil 95.
• Nuevos Límites:
  • El enfoque descubrió 25 nuevos límites inferiores y cinco nuevas mejores soluciones (límites superiores).
  • Ocho de los nuevos límites inferiores fueron verificados directamente por las restricciones inferidas sin requerir ninguna búsqueda.
• Sobrecarga de Preprocesamiento: La fase de preprocesamiento (generación de coberturas y levantamiento) típicamente tomó solo unos pocos segundos. Las instancias donde tomó más tiempo (>1 minuto) fueron exclusivamente instancias de gran escala (UBO500/UBO1000) con más de 500 tareas.
• Tipos de Restricciones: Las ganancias más significativas se observaron cuando la mejor restricción inferida era disyuntiva (capacidad unitaria), aunque las restricciones cumulativas generales también proporcionaron mejoras moderadas.

Significación y Reivindicaciones

El artículo afirma que este enfoque retiene con éxito los rasgos positivos del método UNL (ganancias sustanciales en instancias con estructuras ocultas) mientras evita su principal debilidad (inestabilidad y ralentizaciones severas en instancias sin tales estructuras).

Al interpretar las restricciones cumulativas a través de la lente de la geometría poliédrica, el método proporciona una forma sistemática de fortalecer los modelos con desigualdades válidas. Los autores enfatizan que este es un método de preprocesamiento; no reemplaza al solver, sino que mejora la instancia de entrada. Los resultados sugieren que inferir restricciones mediante levantamiento es una estrategia robusta para avanzar en el estado del arte en benchmarks de planificación, particularmente para ajustar los límites inferiores y reducir el esfuerzo de búsqueda, sin el riesgo de las ralentizaciones de "un orden de magnitud" asociadas con las técnicas de sondeo dinámico anteriores.