Imagine you are an administrator of a large estate with many towns, villages and a network of roads connecting them. You have already got tired of all the daily duties and you decide to divide the whole land into smaller districts and to delegate the administration duties to your deputies, each deputy controls one district.
The goal is to divide the original area into maximally autonomous regions, i.e., minimally interconnected regions.
Input: Graph <latex>$G(V,E)$</latex>, where V is a set of towns <latex>${v_1,…,v_M}$</latex> and E is a set of roads connecting the towns. n is the number of regions to which the whole area is to be divided.
Output: Partitioning of the set V into equally-sized and disjoint subsets <latex>${V_1,…,V_n}$</latex>, where <latex>$\bigcup_{i=1}^{n}V_i=V$</latex> and <latex>$||V_i|-|V_j||\leq 1$</latex> for all <latex>$i\neq j$</latex> such that the inter-connectivity of the regions is minimized subject to the constraint imposed on the regions size.
The number of roads interconnecting towns from different regions. This means, the number of all roads between towns $t_i$ and $t_j$, where $t_i$ belongs to different region than $t_j$.
<latex> \begin{equation*} f(s) = \sum_{l\in V_i, k\in V_j,i\neq j}e_{lk} \end{equation*} </latex>
This function is to be minimized.
It is possible to solve this problem as the multi-objective one
This way it might be possible to find regions of great autonomy while being of very similar size.