The Balanced Connected k-Partition Problem: Polyhedra and Algorithms - Ota, Matheus J.; Miyazawa, Flávio K.; Moura, Phablo F. S. (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2021: Anais do XXXIV Concurso de Teses e DissertaçõesDO - 10.5753/ctd.2021.15763, 2021)
The balanced connected k-partition (BCP k ) problem consists in partitioning a connected graph into connected subgraphs with similar weights. This problem arises in multiple practical applications, such as police patrolling, image processing, data base and operating systems. In this work, we address the BCP k using mathematical programming. We propose a compact formulation based on flows and a formulation based on separators. We introduce classes of valid inequalities and design polynomial-time separation routines. Moreover, to the best of our knowledge, we present the first polyhedral study for BCP k in the literature. Finally, we report on computational experiments showing that the proposed algorithms significantly outperform the state of the art for BCP k .