Organizing National Elections in India to Elect the 543 Members of the Lok Sabha - Nag, Bodhibrata; Murty, Katta (Algorithmic Operations Research, 2012)
There are 833 thousand polling stations in all of the 543 parliamentary constituencies spread over 35 states of India. On the day elections are being held in any one of these polling stations, a minimum of 4 Central Police Force(CPF) personnel must be deployed there, to maintain law and order and guarantee that voters can vote freely without being intimidated by anyone. As the number of CPF personnel available for this activity is limited, it is not possible to hold the Indian General elections on a single day over the whole country. So the set of 35 States of India is partitioned into a number of subsets, with elections in each subset of states being held on a single day. This partition is required to satisfy the constraints that the states in each subset are contiguous, and the subsets themselves must be contiguous. We present a method for organizing the Indian General Elections subject to these constraints, and minimizing the total number of election days required, and the total cost for the movement of CPF personnel involved. The method is based on the shortest Hamiltonian path problem, a tour segmentation problem defined in the paper, and the bipartite minimum cost flow problem.