Resumo Técnico: Sobre a Inferência de Restrições Cumulativas

Definição do Problema

As restrições cumulativas são um pilar da programação com restrições (CP) para escalonamento, modelando recursos renováveis limitados. No entanto, as técnicas de propagação padrão geralmente raciocinam sobre cada restrição de recurso de forma independente. Esse "ponto de vista de recurso único" falha em capturar interações entre múltiplos recursos, levando a uma degradação severa de desempenho em benchmarks específicos (ex: a estrutura do problema "3n").

Tentativas anteriores para abordar isso, como a abordagem "Unite and Lead" (UNL) de Sidorov et al. [2025a], identificaram com sucesso estruturas disjuntivas ocultas (conjuntos de tarefas que não podem ser executadas em paralelo). Contudo, o UNL sofre de duas limitações críticas:

1. Falta de Generalidade: É restrito ao raciocínio disjuntivo e não consegue derivar interações multi-recurso mais gerais.
2. Sobrecarga de Busca (Search Overhead): Requer a sondagem explícita de cliques disjuntivos durante a busca, incorrendo em uma sobrecarga significativa que frequentemente retarda os solvers em ordens de magnitude em instâncias que carecem de tais estruturas.

O problema central abordado neste artigo é como inferir interações multi-recurso válidas e fortalecer o modelo sem incorrer nas penalidades de tempo de busca associadas à detecção dinâmica de cliques.

Metodologia

A abordagem proposta reformula as restrições cumulativas como desigualdades lineares sobre vetores de ocupação e aplica técnicas de geometria poliédrica e programação inteira mista (MIP) para inferir novas restrições no nó raiz (pré-processamento).

1. Fundamentação Teórica

O método baseia-se na representação dos tempos de início $s_i$ e durações $d_i$ das tarefas como vetores de ocupação $\langle s_i | d_i \rangle$, onde o vetor é 1 durante o intervalo $[s_i, s_i + d_i)$ e 0 caso contrário. Uma restrição cumulativa $\sum r_i \langle s_i | d_i \rangle \le C$ é, portanto, vista como uma desigualdade linear.

• O Lema 7 estabelece que qualquer desigualdade válida para o poliedro definido pelos vetores de ocupação corresponde a uma restrição cumulativa válida para o problema de escalonamento original.
• Isso permite que o problema de inferência de restrições seja tratado como a geração de planos de corte (cutting planes) válidos.

2. O Fluxo de Trabalho Baseado em Levantamento (Lifting)

Em vez de buscar por cliques disjuntivos dinamicamente, o algoritmo realiza uma etapa de pré-processamento estático envolvendo três estágios:

1. Descoberta de Coberturas (Cover Discovery): O algoritmo enumera "coberturas" (conjuntos de tarefas $C$ onde a soma dos requisitos de recurso excede a capacidade, ou seja, $\sum_{i \in C} r_i > C$). Ele gera coberturas "curtas" (cardinalidade 2 e 3) e coberturas "longas" (agrupadas por valores de consumo de recurso) e seleciona os candidatos mais promissores com base em uma métrica de limite de capacidade ($L$), que estima o makespan mínimo abrangido pelas tarefas.
2. Levantamento (Lifting): Para cada cobertura descoberta, o método aplica o procedimento de levantamento (Padberg, 1975). Isso fortalece a desigualdade de cobertura básica ($\sum_{i \in C} x_i \le |C| - 1$) ao determinar o coeficiente máximo $\beta$ para variáveis que não estavam originalmente na cobertura, de modo que a desigualdade $\sum_{i \in C} x_i + \beta x_j \le |C| - 1$ permaneça válida. Isso é alcançado resolvendo subproblemas auxiliares (maximizando o lado esquerdo da desigualdade atual sob restrições específicas).
3. Injeção de Restrições: As desigualdades levantadas resultantes são convertidas de volta em novas restrições cumulativas e injetadas na instância do problema antes que o solver de CP inicie sua busca.

A implementação utiliza o Gurobi 12 para resolver os subproblemas de levantamento e limita o número de restrições geradas ($N_{out}$) e as coberturas iniciais ($N_{cover}$) para controlar o tempo de pré-processamento.

Principais Contribuições

• Estrutura Algorítmica: Um novo método para inferir restrições cumulativas que generaliza além do raciocínio disjuntivo, capturando interações multi-recurso através de desigualdades válidas.
• Estratégia de Pré-processamento: Uma abordagem de nó raiz que evita a sobrecarga de tempo de busca da detecção dinâmica de cliques, eliminando assim a instabilidade observada nos métodos anteriores baseados em UNL.
• Integração de Técnicas de MIP: A aplicação de levantamento e desigualdades de cobertura da programação inteira ao domínio do escalonamento em programação com restrições.
• Métrica de Qualidade: A introdução da razão de limite de capacidade como uma heurística para selecionar quais coberturas levantar e quais restrições inferidas manter.

Resultados Experimentais

O método foi avaliado em benchmarks padrão RCPSP (736 instâncias) e RCPSP/max (349 instâncias) utilizando solvers de última geração (Pumpkin e CP-SAT).

• Ganhos de Desempenho:
  • Otimalidade: Para instâncias resolvidas até a otimalidade, o levantamento reduziu significativamente o tempo de resolução, por vezes de dezenas de minutos para frações de segundo.
  • Progresso da Busca: Em instâncias não resolvidas até a otimalidade, a abordagem melhorou substancialmente o integral duplo (taxa de melhoria do limite inferior), indicando uma convergência mais rápida para limites estreitos.
  • Estabilidade: Ao contrário do UNL, a degradação de desempenho (aumento no tempo de resolução) foi rara. Apenas 19 pares de execuções mostraram lentidão significativa, e mesmo o evento de "degradação de 2x" ocorreu apenas no percentil 95.
• Novos Limites:
  • A abordagem descobriu 25 novos limites inferiores e cinco novas melhores soluções (limites superiores).
  • Oito dos novos limites inferiores foram verificados diretamente pelas restrições inferidas sem a necessidade de busca.
• Sobrecarga de Pré-processamento: A fase de pré-processamento (geração de cobertura e levantamento) normalmente levou apenas alguns segundos. Instâncias onde levou mais tempo (>1 minuto) foram exclusivamente instâncias de grande escala (UBO500/UBO1000) com mais de 500 tarefas.
• Tipos de Restrição: Os ganhos mais significativos foram observados quando a melhor restrição inferida era disjuntiva (capacidade unitária), embora restrições cumulativas gerais também tenham proporcionado melhorias moderadas.

Significância e Alegações

O artigo afirma que esta abordagem consegue reter os traços positivos do método UNL (ganhos substanciais em instâncias com estruturas ocultas) enquanto evita sua principal fraqueza (instabilidade e lentidões severas em instâncias sem tais estruturas).

Ao interpretar as restrições cumulativas através da lente da geometria poliédrica, o método fornece uma maneira sistemática de fortalecer modelos com desigualdades válidas. Os autores enfatizam que este é um método de pré-processamento; ele não substitui o solver, mas melhora a instância de entrada. Os resultados sugerem que inferir restrições via levantamento é uma estratégia robusta para avançar o estado da arte em benchmarks de escalonamento, particularmente para estreitar limites inferiores e reduzir o esforço de busca, sem o risco das lentidões de "ordem de magnitude" associadas às técnicas anteriores de sondagem dinâmica.