🔢 mathematics

A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem

Este artigo apresenta um algoritmo de branch-price-and-cut numericamente seguro com uma estratégia de precificação por programação dinâmica eficiente que supera significativamente os métodos existentes para o problema de partição de ciclos com restrição de comprimento, resolvendo instâncias maiores e fechando casos anteriormente não resolvidos.

Autores originais: Mohammed Ghannam, Ambros Gleixner, Gioni Mexi, Edward Lam

Publicado 2026-07-20✓ Author reviewed ⓘ

📖 3 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Mohammed Ghannam, Ambros Gleixner, Gioni Mexi, Edward Lam

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é o gerente de uma frota de drones de entrega. Cada entrega que você faz é em um local diferente, mas cada parada no seu mapa deve ser visitada regularmente e tem uma regra muito específica e não negociável: existe um "tempo crítico" para cada ponto visitado, que é o tempo máximo que pode passar antes que aquele local precise ser atendido novamente. Alguns locais são extremamente urgentes e precisam ser atendidos rapidamente, enquanto outros podem esperar um pouco mais. Seu trabalho é descobrir a maneira mais eficiente de agrupar todas as suas paradas de entrega em loops. Você quer usar o menor número possível de drones, mas cada loop que você criar deve ser curto o suficiente para que o tempo de viagem não exceda o menor tempo crítico entre todos os pontos visitados naquele grupo. Este é um quebra-cabeça de geometria e tempo, um problema que matemáticos chamam de "Problema de Partição de Ciclos com Restrição de Comprimento". É o tipo de desafio que aparece na vida real, como agendar patrulhas de segurança para uma cidade ou organizar trocas de rins, mas resolvê-lo perfeitamente é notoriamente difícil. É como tentar resolver um quebra-cabeça de peças gigantes onde as peças mudam de forma dependendo de como você tenta encaixá-las.

Este artigo apresenta uma nova maneira superinteligente de resolver esse quebra-cabeça, que não é apenas mais rápida, mas também incrivelmente cuidadosa com sua matemática. Os autores, uma equipe de pesquisadores da Alemanha e da Austrália, construíram um algoritmo de "branch-price-and-cut" (ramificação, preço e corte). Pense nisso como um detetive que não apenas adivinha onde estão as pistas, mas constrói sistematicamente um mapa de cada solução possível, descartando as impossíveis e "precificando" as promissoras para encontrar a melhor rota absoluta. A arma secreta deles é uma técnica chamada "geração de colunas", que é como construir uma casa encomendando apenas os tijolos específicos que você precisa agora, em vez de tentar transportar uma montanha inteira de tijolos para o canteiro de obras de uma só vez. Eles também adicionaram um recurso de "segurança numérica", que é como um sistema de dupla checagem que garante que o computador não cometa pequenos erros de arredondamento que poderiam levar a uma resposta errada.

Os resultados são impressionantes. A equipe testou seu método em 84 instâncias diferentes de quebra-cédulas, variando de configurações pequenas com 14 nós até massivas com 100 nós. Seu novo algoritmo conseguiu resolver 52 dessas instâncias com perfeição comprovada, incluindo uma com 76 nós — um tamanho que nunca havia sido resolvido antes (o recorde anterior era de 52 nós). Eles encerraram 14 instâncias que eram anteriormente insolúveis. Em termos de velocidade, seu método foi, em média, 14,7 vezes mais rápido do que a melhor abordagem anterior. Eles descobriram que os truques mais importantes foram a "quebra de simetria" (dizer ao computador para não perder tempo verificando o mesmo loop duas vezes apenas porque ele começou de um ponto diferente) e a "busca bidirecional" (construir o loop de ambos os lados ao mesmo tempo e se encontrar no meio). Embora tenham tentado adicionar "planos de corte" extras (regras matemáticas para podar opções ruins), eles descobriram que, para a maioria dos casos, o quebra-cabeça já era tão apertado que essas regras extras não ajudavam muito e, às vezes, até desaceleravam o processo. O artigo conclui que, embora tenham decifrado o código para até 76 nós, o verdadeiro gargalo agora é a velocidade da rotina de precificação, e resolver quebra-cabeças ainda maiores provavelmente exigirá truques computacionais ainda mais poderosos.

Resumo Técnico: Um Algoritmo de Branch-Price-and-Cut Numericamente Seguro para o Problema de Partição de Ciclos com Restrição de Comprimento

1. Definição do Problema

O Problema de Partição de Ciclos com Restrição de Comprimento (LCCP) é um problema de otimização em grafos definido em um grafo não direcionado $G=(V, E)$ . O objetivo é particionar o conjunto de nós $V$ no número mínimo de ciclos disjuntos, de modo que cada nó $i$ seja coberto exatamente uma vez.

Cada nó $i$ está associado a um tempo crítico $q_i > 0$ , e cada aresta $\{i, j\}$ possui um tempo de viagem $t_{i,j} \ge 0$ . Um ciclo $C$ é considerado viável em comprimento se seu tempo total de viagem não exceder o tempo crítico de qualquer nó contido nele:
$t(C) := \sum_{\{i,j\} \in C} t_{i,j} \le \min_{i \in C} \{q_i\}$
O problema é conhecido por ser NP-difícil (redutível do Problema do Caixeiro Viajante) e não admite um algoritmo de aproximação em tempo polinomial. As abordagens anteriores de estado da arte utilizaram formulações compactas de Programação Inteira Mista (MIP) (baseadas em Miller-Tucker-Zemlin ou Restrições de Eliminação de Subtours), que conseguiam resolver instâncias de até 52 nós.

2. Metodologia

Os autores propõem um algoritmo exato de Branch-Price-and-Cut (BPC) baseado em uma formulação de Partição de Conjuntos (SP).

2.1 Formulação de Partição de Conjuntos

Em vez de formulações compactas, o problema é modelado como um problema de partição de conjuntos onde as variáveis representam ciclos inteiros viáveis em comprimento. A formulação minimiza $\sum_{C \in \Omega} \lambda_C$ sujeito a restrições de cobertura $\sum_{C \in \Omega} a^C_i \lambda_C = 1$ para todo $i \in V$ . Devido ao tamanho exponencial de $\Omega$ , os autores empregam Geração de Colunas para resolver a Relaxação de Programação Linear (LP) dinamicamente.

2.2 O Problema de Preço (LCPCCP)

A tarefa computacional central é o Problema de Ciclo com Coleta de Prêmios e Restrição de Comprimento (LCPCCP), que busca um ciclo com custo reduzido negativo. Este problema é fortemente NP-difícil. Os autores o resolvem usando:

Programação Dinâmica (DP): Um algoritmo de definição de rótulos (label-setting) onde os rótulos rastreiam nós visitados, custo reduzido, tempo total de viagem e o tempo crítico mínimo do caminho.
Busca Bidirecional: Explorando a natureza não direcionada do grafo, o algoritmo estende os rótulos a partir de um nó inicial $s$ apenas até que $t(\ell) < q(\ell)/2$ . Rótulos não dominados de buscas direta e reversa são então fundidos para formar ciclos completos. Isso reduz significativamente o espaço de busca em comparação com a busca monodirecional.
Regras de Dominância: Os rótulos são podados se outro rótulo no mesmo nó possuir um custo reduzido menor ou igual, um tempo de viagem menor ou igual e um subconjunto de nós visitados.
Relaxação ng: Para lidar com ciclos não elementares (revisitação de nós), os autores utilizam uma relaxação de caminho ng com expansão dinâmica de vizinhança. Isso fornece limites inferiores válidos enquanto evita a complexidade de impor a elementaridade estritamente durante as fases iniciais de busca.
Heurística Gulosa: Uma heurística rápida é executada primeiro para encontrar ciclos de melhoria através da remoção de nós duais negativos ou inserção de nós duais positivos, reduzendo a necessidade de iterações dispendiosas de DP.

2.3 Exploração de Estrutura

Desigualdade Triangular: Para nós onde a desigualdade triangular se mantém localmente, os autores alternam para restrições de cobertura de conjuntos. Isso restringe as variáveis duais a serem não negativas, permitindo a remoção de nós com dual zero durante o preço e possibilitando a poda preventiva.
Quebra de Simetria: Para evitar a geração do mesmo ciclo a partir de diferentes nós de partida, a busca é restrita a visitar apenas nós com tempos críticos maiores ou iguais ao tempo crítico do nó inicial (com desempate por índice).

2.4 Planos de Corte (Cutting Planes)

O algoritmo integra duas famílias de cortes:

Cortes de Linha de Subconjunto (SRCs): Aplicados a subconjuntos de nós para limitar o número de ciclos que os cobrem.
Cortes de Clique (CCs): Baseados no grafo de conflito dos ciclos.
Os autores investigam o respeito a esses cortes dentro do problema de preço. Eles observam que, embora os cortes de Clique sejam ignorados no preço para evitar complexidade, os Cortes de Linha de Subconjunto são respeitados ao aumentar os rótulos com recursos adicionais, o que melhora a convergência em instâncias específicas difíceis.

2.5 Segurança Numérica

Uma contribuição fundamental é a implementação de limites numericamente seguros. A aritmética de ponto flutuante pode levar a soluções duais inviáveis devido a erros de arredondamento. Os autores propõem um mecanismo de reparo dual:

Escalar os duais de ponto flutuante para inteiros grandes.
Verificar a viabilidade dual exatamente usando aritmética de inteiros.
Se for inviável, reduzir o fator de escala e tentar novamente.
Isso garante que os limites inferiores usados para o branching sejam matematicamente rigorosos, impedindo que o algoritmo alegue otimalidade baseada em artefatos numéricos.

2.6 Branching e Heurísticas

Branching: Utiliza primordialmente Edge Branching (fixando arestas para estarem ou não na solução). O Ryan-Foster branching (sobre pares de nós) foi testado, mas considerou-se menos robusto para esta estrutura específica de problema.
Heurísticas: Uma variante de branch-and-price heurística relaxa as regras de dominância para encontrar soluções primais de alta qualidade rapidamente, que são então usadas como warm starts para o solver exato.

3. Principais Contribuições

Formulação de Partição de Conjuntos: Demonstra que uma abordagem baseada em SP produz relaxações de LP significativamente mais estreitas (gap médio de raiz de 0,4%) comparado às formulações compactas anteriores (gap de 30,3%).
Preço por DP Bidirecional: Introduz uma busca bidirecional eficiente para o problema de preço LCPCCP, aproveitando a simetria de grafos não direcionados para reduzir o espaço de busca.
Segurança Numérica: Fornece um framework para obter limites inferiores provadamente corretos em um ambiente de branch-and-price combinando solvers de ponto flutuante com aritmética de inteiros exata para verificação dual.
Integração Algorítmica: Combina preço guloso, relaxação ng, quebra de simetria e gestão específica de cortes em um solver coeso.

4. Resultados Computacionais

O algoritmo foi testado em 84 instâncias de referência (14 a 100 nós) contra o método anterior de estado da arte (branch-and-cut, bnc-sec).

Desempenho: O proposto algoritmo de Branch-Price-and-Cut (especificamente a configuração withsrc+pricing) resolveu 52 instâncias até a otimalidade provada, comparado a 40 do método anterior mais eficiente.
Escala: Conseguiu resolver instâncias com até 76 nós, fechando 14 instâncias anteriormente insolúveis. O limite anterior era de 52 nós.
Velocidade: O núcleo de branch-and-price é, em média, 14,7 vezes mais rápido que a abordagem anterior mais eficiente.
Eficiência do Nó Raiz: 49 das 52 instâncias resolvidas foram solucionadas no nó raiz sem necessidade de branching, destacando a força da relaxação de LP.
Sobrecarga de Segurança Numérica: A versão numericamente segura resolveu o mesmo número de instâncias que a versão não segura, mas foi aproximadamente 40% mais lenta (média geométrica de 7,6s vs 4,5s). No entanto, nenhum resultado incorreto foi detectado na versão não segura, e a sobrecarga é considerada moderada dada a garantia de correção.

5. Significância e Alegações

O artigo afirma que a formulação de partição de conjuntos é o principal motor de desempenho, fornecendo limites estreitos que permitem que a maioria das instâncias seja resolvida no nó raiz. A busca bidirecional e a quebra de simetria são identificadas como os componentes algorítmicos mais impactantes para reduzir o tempo de execução.

Os autores observam modestamente que, embora o método melhore significativamente o estado da arte, instâncias além de 76 nós permanecem insolúveis, e a rotina de preço continua sendo o gargalo computacional. Eles sugerem que melhorias futuras podem exigir limites duais mais fortes ou algoritmos de preço mais escaláveis (ex: aceleração por GPU). O trabalho estabelece um novo patamar para resolver o LCCP, provando que métodos exatos podem lidar com instâncias maiores e mais complexas quando combinados com técnicas de exploração de estrutura e segurança numérica.