On the Partition of an Administrative Region into Homogeneous District

We consider the problem of partitioning a given region into connected districts and assigning them to administrative officers. The officer in charge of a district takes care of all the activities in which the municipalities of that district are involved. An activity corresponds to a task which requires the coordination of a subset of municipalities; it implies for the officer in charge a fixed workload for the task, plus a variable workload proportional to the number of municipalities involved. If the subset of municipalities associated to an activity is divided into several districts, the fixed workload is required to each of the corresponding officers, thus leading to a duplication. The problem requires to balance the officer workload and minimize duplications. We model the problem as that of finding a suitable balanced partition into trees of a node weighted undirected graph. We propose compact and extended formulations, reduction procedures for generating valid inequalities for both formulations, a column generation approach, a cutting plane algorithm for the pricing problem, and local search algorithms for the general and the pricing problems. We provide computational results for random instances and for two real-world instances (Milano and Monza provinces).