Forest-Based Formulation for the Balanced Connected k-Partition Problem

Partitioning a graph into a fixed number of connected subgraphs with approximately equal weights is a fundamental problem in the fields of graph theory and combinatorial optimization. This problem finds applications in various domains such as farmland allocation, political districting, and sales territory design. However, existing mixed-integer programming (MIP) formulations for this problem struggle to handle large-scale problems, particularly as the number of required subgraphs increases, thereby limiting their practical applicability in real-world scenarios. In this paper, we propose a more compact forest-based formulation for this problem and validate its efficiency and scalability through computational experiments. It has been integrated into our sales territory design system.