The Balanced Connected k-Partition Problem: Polyhedra and Algorithms

• Matheus J. Ota UNICAMP http://orcid.org/0000-0002-3730-6420
• Flávio K. Miyazawa UNICAMP https://orcid.org/0000-0002-1067-6421
• Phablo F. S. Moura UFMG https://orcid.org/0000-0002-8176-0874

DOI: https://doi.org/10.5753/ctd.2021.15763

Resumo

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.

Palavras-chave: mathematical programming, combinatorial optimization, graph theory, graph partition

Referências

de Aragão, M. P. and Uchoa, E. (1999). The γ-connected assignment problem. European Journal of Operational Research, 118(1):127–138.

Dyer, M. and Frieze, A. (1985). On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics, 10(2):139–153.

Lovász, L. (1977). A homology theory for spanning tress of a graph. Acta Mathematica Academiae Scientiarum Hungarica, 30:241–251.

Matić, D. (2014). A mixed integer linear programming model and variable neighborhood search for maximally balanced connected partition problem. Applied Mathematics and Computation, 237:85–97.

Miyazawa, F. K., Moura, P. F., Ota, M. J., and Wakabayashi, Y. (2021). Partitioning a graph into balanced connected classes: Formulations, separation and experiments. European Journal of Operational Research, 293(3):826–836.

Miyazawa, F. K., Moura, P. F. S., Ota, M. J., and Wakabayashi, Y. (2020). Cut and flow formulations for the balanced connected k-partition problem. In International Symposium on Combinatorial Optimization, pages 128–139. Springer.

Ota, M. J. (2020). The balanced connected k-partition problem : polyhedra and algorithms. Master’s thesis, Universidade Estadual de Campinas.

Zhou, X., Wang, H., Ding, B., Hu, T., and Shang, S. (2019). Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm. Expert Systems with Applications, 116:10–20.