Optimal political districting

For the political districting problem, I propose the following solution methodology: (a) use Lagrangian relaxation to determine the centres of the districts, then, (b) use the transportation technique to assign population units to centres, and finally, (c) resolve the splitting problem by solving a sequence of capacitated transportation problems. This method is applied to the problem of determining the provincial districts for the City of Saskatoon, Canada, and the results are compared with the actual districting done in 1993 by the Electoral Boundaries Commission.