Algoritmos para o Bi-Objective Balanced Multiway Cut Problem

Neste artigo abordamos o Bi-Objective Balanced Multiway Cut Problem, uma variação NP-Difícil do clássico problema do Corte Mínimo, na qual deseja-se encontrar um conjunto de arestas que quando removidas particionam o grafo em diversas componentes, de forma que cada uma possua exatamente um terminal. Desejamos soluções que minimizem tanto o custo do conjunto de aresta removidas, quanto o tamanho da maior componente. Como muitas vezes esses objetivos entram em conflito, buscamos encontrar uma coleção de soluções não dominadas. Para tanto, utilizamos abordagens exatas e heurísticas, usando o resolvedor CPLEX e a meta-heurística evolutiva Non-dominated Sorting Biased Random-Key Genetic Algorithm, respectivamente. Experimentos computacionais em instâncias da literatura mostram que a abordagem exata obtém fronteiras não dominadas para algumas instâncias, mas é superada pela maioria das heurísticas. Entre as heurísticas, as estratégias baseadas em coloração de vértices atingem os melhores resultados.