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).