Exact and Heuristic Approaches for the Edge Clique Cover Problem

O Problema de Cobertura de Arestas por Cliques (ECCP) busca encontrar o número mínimo de cliques que cobrem todas as arestas de um grafo dado. Apesar de sua importância fundamental em otimização combinatória e em muitas aplicações tais como geometria computacional, análise de redes, etc., o ECCP permanece computacionalmente desafiador devido à sua natureza NP-difícil e à sua resistência ao desenvolvimento de algoritmos aproximativos em tempo polinomial. Esta tese apresenta uma investigação abrangente de formulações do Problema de Cobertura de Conjuntos (SCP) para o ECCP, desenvolvendo tanto estruturas heurísticas avançadas quanto métodos exatos de solução inovadores. A Parte I introduz estruturas conceituais para projeto de algoritmos através de amostragem sistemática de cliques, desenvolvendo a Heurística de Amostragem de Cliques (CSH), a Heurística de Amostragem por Custo Reduzido (RCSH), e a RCSH aprimorada com Busca Local (LS-RCSH) que geram formulações restritas de alta qualidade e superam significativamente heurísticas tradicionais para ECCP. A Parte II aborda limitações fundamentais que impedem algoritmos exatos robustos introduzindo uma estrutura branch-and-price baseada em transformação sistemática de grafos do ECCP para Problemas de Cobertura de Vértices por Cliques (VCCP) equivalentes, permitindo adaptação de estratégias de ramificação, proveniente do Problema de Coloração de Grafos, enquanto preserva a estrutura do Problema de Clique de Peso Máximo ao longo das árvores de enumeração. Adicionalmente, desenvolvemos uma formulação VCCP novel baseada em representantes com estratégias de redução sistemática que serve tanto como método independente quanto benchmark para a abordagem branch-and-price. Experimentos computacionais extensivos através de diversas classes de instâncias revelam regimes de desempenho distintos onde instâncias menores e mais esparsas permanecem tratáveis para métodos exatos enquanto grafos maiores e mais densos apresentam desafios computacionais significativos. As estruturas heurísticas demonstram desempenho robusto através de todo o espectro de testes, com LS-RCSH alcançando equilíbrio entre qualidade de solução e eficiência, enquanto o método branch-and-price exato fornece com sucesso limites significativos em algumas instâncias onde formulações SCP diretas falham. As contribuições estendem-se além de desenvolvimentos algorítmicos específicos para incluir insights metodológicos em problemas de otimização baseados em cliques, técnicas sistemáticas de formulação SCP, e adaptação principiada de estratégias de ramificação que estabelecem fundações para pesquisas futuras neste domínio desafiador da otimização combinatória.