The Balanced Connected k-Partition Problem: Polyhedra and Algorithms
ResumoThe balanced connected k-partition (BCPk) 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 BCPk 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 BCPk in the literature. Finally, we report on computational experiments showing that the proposed algorithms significantly outperform the state of the art for BCPk.
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.