Múltiplos decodificadores para resolver o Multiway Cut Problem com a meta-heurística MP-BRKGA

No Multiway Cut Problem (MCP) temos um grafo não direcionado G = (V, E) com custos não negativos nas arestas, e um conjunto S = {s₁, s₂, ..., s_k} ⊆ V de vértices conhecidos como terminais. Queremos encontrar um conjunto F ⊆ E de arestas com custo mínimo cuja remoção desconecta todos os k terminais. Neste contexto, um corte C_i é definido como o conjunto de nós alcançáveis em (V, E \ F) pelo terminal s_i em S, enquanto F_i = δ(C_i) é o conjunto de todas as arestas que compõem a fronteira de C_i, ou seja, possuem uma única extremidade em C_i. Este problema é uma versão NP-Difícil do clássico problema do corte mínimo, e surge em aplicações de áreas como computação distribuída e segmentação de imagens.

Neste trabalho propomos uma variedade de decodificadores que utilizam a meta-heurística evolutiva Multi-Parent Biased Random-Key Genetic Algorithm para encontrar boas soluções para instâncias do MCP. Os decodificadores projetados utilizam abordagens baseadas em threshold, coloração de vértices, algoritmo para árvore geradora mínima e isolation heuristic, além de possuírem estratégias de perturbação de custos, correção de inviabilidade e eliminação de componentes isolados, que aprimoram a solução codificada por cada indivíduo da população. Os decodificadores podem ser adaptados para outras meta-heurísticas ou usados de forma independente. 

Realizamos uma análise computacional detalhada utilizando as maiores instâncias de Bloch-Hansen et al. (2023). Em particular, executamos nossos métodos para instâncias com 320 vértices, variando o número de terminais em {20, 40, 60} e a quantidade de arestas entre 1 e 6 vezes o número de vértices. Os testes mostram que dois dos nossos decodificadores (a saber, um baseado em coloração e outro no algoritmo de Kruskal) atingem o ótimo para as 60 instâncias utilizadas em menos de 1 minuto por instância.