Pesquisa operacional aplicada ao One-Sided Crossing Minimization (OSCM) em grafos bipartidos.

Abstract

A minimização de cruzamentos de arestas constitui um dos principais critérios de qualidade em desenhos de grafos, influenciando diretamente sua legibilidade e interpretabilidade. Nesse contexto, o Problema de Minimização de Cruzamentos Unilaterais (OneSided Crossing Minimization - OSCM) consiste em determinar uma ordenação para os vértices da camada livre de um grafo bipartido, mantendo fixa a ordenação da camada adjacente, de modo a minimizar o número de cruzamentos entre as arestas. Trata-se de um problema NP-difícil, com aplicações em áreas como desenho hierárquico de grafos, visualização de software e projeto de circuitos integrados (Very Large Scale Integration - VLSI). Este trabalho apresenta o desenvolvimento de métodos heurísticos para a resolução do OSCM. A metodologia proposta combina heurísticas construtivas para geração de soluções iniciais, procedimentos de busca local para refinamento das soluções e uma metaheurística Simulated Annealing (SA), responsável por intensificar a exploração do espaço de busca. Foram implementadas as heurísticas do Baricentro e da Mediana, as estruturas de vizinhança Swap, Insert e 2-Opt, além do método Variable Neighborhood Descent (VND). Para acelerar a avaliação da função objetivo, foi empregada uma matriz de cruzamentos, permitindo o cálculo incremental das variações provocadas pelos movimentos de vizinhança. Os parâmetros do SA foram calibrados por meio da ferramenta iRace. Os experimentos computacionais foram realizados utilizando instâncias do Parameterized Algorithms and Computational Experiments Challenge (PACE) Challenge 2024. Inicialmente, foram conduzidos testes em um conjunto de 20 instâncias para comparar o desempenho das heurísticas construtivas, das buscas locais e da metaheurística proposta. Em seguida, o SA foi avaliado em 196 instâncias do conjunto oficial da competição. Os resultados mostraram que a heurística da Mediana produziu soluções iniciais de melhor qualidade que a heurística do Baricentro e que a integração entre a solução inicial, os procedimentos de refinamento e o Simulated Annealing proporcionou melhorias expressivas na qualidade das soluções. A abordagem proposta reduziu o Desvio Médio Relativo (DMR) de 8,20% para 0,75% em relação às melhores soluções conhecidas do PACE Challenge 2024, alcançando um DMR de apenas 0,24% quando desconsiderada uma instância específica que não apresentou melhoria. Esses resultados evidenciam a eficácia da combinação entre heurísticas construtivas, busca local e metaheurística na resolução do OSCM, produzindo soluções satisfatórias para instâncias de diferentes características.