The Balanced Connected k-Partition Problem: Polyhedra and Algorithms

O problema da k-partição conexa balanceada (em inglês, "balanced connected k-partition problem" ou BCPk) consiste em particionar um grafo conexo em subgrafos conexos de pesos semelhantes. Esse problema é conhecido por ser NP-difı́cil e possui diversas aplicações, como patrulhamento policial, processamento de imagem e sistemas operacionais. Nesse trabalho propomos duas formulações para o BCPk , uma baseada em fluxos e outra baseada em cortes. A formulação de fluxos possui um número polinomial de restrições, enquanto a formulação de cortes possui um número exponencial de desigualdades que podem ser separadas em tempo polinomial. Nós introduzimos novas desigualdades válidas para esse último modelo e desenvolvemos rotinas de separação correspondentes. Além disso, nós apresentamos o primeiro estudo poliédrico para o problema. Por fim, nós conduzimos experimentos computacionais em instâncias da literatura e em novas instâncias inspiradas em uma aplicação real. Os resultados mostram que nossas abordagens possuem um desempenho significativamente superior ao estado da arte para o BCPk.