A new integer linear programming formulation for the problem of political districting

Abstract

The problem of dividing political territories in electoral process is a very important factor which contributes to the development of democracy in modern political systems. The most significant criteria for fairness of electoral process are demographic, geographic and political. Demographic criterion in the first place refers to the population equality, while the geographic one is mostly represented by compactness, contiguity and integrity. In this paper we propose a new integer linear programming formulation for the problem of political districting. The model is based on the graph representation of political territory, where territorial units are vertices and direct links between them are edges. The correctness of integer linear programming formulation is mathematically proven. In contrast to the most of the previous formulations, all three major criteria, population equality, compactness and contiguity, are completely taken into consideration. There are two models, one which deals with afore mentioned criteria where compactness is taken as an objective function, and the other one which takes into account interests of the decision maker, i.e. the political ruling body which organizes elections. Several numerical examples for the presented models are given which illustrate general aspects of the problem. The experimental results are obtained using CPLEX solver.