The political districting of Kuwait: Heuristic approaches
Keywords:
Combinatorial optimization, constraint propagation, heuristics, integer programming, multiple objective.Abstract
This paper models the political districting of Kuwait as a multiple objective combinatorialoptimization problem, where each political system is assessed in terms of population andvoting equity, geographical contiguity, and social, religious, ethnic, family size, and educationalhomogeneity. First, it proposes four constructive heuristics and a specialized simulatedannealing to generate alternative non-dominated districting plans that may "guarantee" anational consensus. Second, it searches for a districting plan that optimizes a set of criteria(classified as hard and soft constraints) using a tree-search based heuristic. The heuristic takesadvantage and combines the orthogonal but complementary strengths of constraint and integerprogramming. Finally, it compares the proposed solution to both the existing and the previouslyapplied patterns. Thus, this paper offer politicians a multiple criteria evaluation method thatthey may apply to choose the most "appropriate" political districting pattern.References
Altman, M. 1997. Is automation the answer? The computational complexity of automated redistricting,
Rutgers Computer & Technology Law Journal. 23(1): 81-142.
Altman, M. & McDonald, M. 2011. BARD: Better Automated Redistricting, Journal of Statistical
Software. 42(4): 1:28.
Bourjolly, J. M., Laporte, G. & Rousseau, J. M. 1981. D´ecoupage electoral automatis´e: Application
`al’ˆIle deMontreal. Information Systems and Operational Research.19:113-124.
Bozkaya, B., Erkut, E. & Laporte, G. 2003. A tabu search heuristic and adaptive memory procedure for
political districting. European Journal of Operational Research. 144 :12-26.
Browdy, M.H. 1990. Simulated annealing: an improved computer model for political redistricting, Yale
Law & Policy Review, 8(163).
Chou, C. I. & Li, S. P. 2006. Taming the gerrymandering Statistical physics approach to political
districting problem. Physics A 369: 799-808.
Chou, C. I. & Li, S. P. 2007. Spin systems and political districting problem. Journal of Magnetism and
Magnetic Materials 310: 2889-2891.
Deckro, R. F. 1979. Multiple objective districting: A general heuristic approach using multiple criteria.
Operational Research Quarterly, 28: 953-961.
Eiselt, H. A. & Laporte, G. 1987. Combinatorial optimization problems with soft and hard requirements.
Journal of the Operational Research Society. 38: 785-795.
El-Farzi, E. & Mitra, G. 1992. Solution of set-covering and set-partitioning problems using assignment
relaxations, Journal of Operations Research Society 43: 483.
Fleischmann, B. & Paraschis, I. N. 1988. Solving a large scale districting problem: A case report.
Computers & Operations Research, 15: 521-533.
Forman, S. L. & Yule, Y. 2003. Congressional districting using TSP-based genatic algorithm. Lecture
Notes in Computer Science, 16: 2072-2083.
Garfinkel, R. S. & Nemhauser, G. L. 1970. Optimal political districting by implicit enumeration
techniques. Management Science, 16(8): 495-508.
George, J. A., Lamar, B. W. & Wallace, C. A. 1997. Political district determination using large-scale
network optimazation. Socio Economics Planning Sciences. 31: 11-28.
Hess, S. W., Siegfeldt, J. B., Whelan, J.N. & Zitlau, P. A. 1965. Nonpartisan political redistricting by
computer. Operations Research, 13(6): 998-1006.
Hojati, M. 1996. Optimal political districting. Computers & Operations Research, 23(12): 1147-1161.
Kaiser, H. 1966. An objective method for establishing legislative districts. Midwest Journal of Political
Science. 10: 200-213.
Kalcsics, J., Nickel, S. & Schroder, M. 2005. Towards a unified territorial design approach-applications,
algorithms and GIS integration. Fraunhofer Institut Techno-und Wirtschaftsmathematik. 13: 1-74.
King, D. M. Jacobson, S. H. & Sewell, E. C. 2014. Efficient geo-graph contiguity and hole algorithms
for geographic zoning and dynamic plane graph partitioning. Mathematical Programming. In press.
Johnston, R. 2002. Manipulating maps and winning elections: measuring the impact of malapportionment
and gerrymandering. Political geography. 21:1-31.
Lewyn, M.E. 1993. How to limit gerrymandering. Florida Law Review. 45: 403-486.
Mehrotra, A., Johnson, EL. & Nemhauser, GL. 1998. An optimization based heuristic for political
districting. Management Science 44: 1100-1114.
Ministry of Planning, Statistics and Census Sector. 2009. Annual Statistics abstract. Edition 46. State
of Kuwait.
Nagel, S. 1965. Simplified bipartisan computer redistricting. Stanford Law Review 17: 863-899.
Nemoto, T. & Hotta, K. 2003. Modelling and solution of the problem of optimal electoral districting.
Communal OR Society Jpn. 48: 300-306.
Nygreen, B. 1988. European assembly constituencies for wales. Comparing of methods for solving a
political districting problem. Mathematical Programming 42: 159-169.
Pukelsheim, F., Ricca, F., Simeone, B., Scozzari, A. & Serafini, P. 2012. Network flow methods for
electoral systems. Networks. 59(1): 73-88
Ricca, F., Scozzari, A. & Simeone, B. 2008. Weighted Voronoi region algorithms for political districting.
Mathematical Computer Modelling, 48: 1468-1477.
Ricca, F., Scozzari A. & Simeone, B. 2013. Political districting: from classical models to recent
approaches. 4OR Quarterly Journal Operations Research. 9(3), 223-254.
Ricca, F. & Simeone, B. 1997. Political districting: traps, criteria, algorithms and trade-offs. Ricerca
Operativa. 27: 81-119.
Ricca, F. & Simeone, B. 2008. Local search algorithms for political districting. European Journal of
Operational Research 189(3): 1409-1426.
Tavares-Pereira, F., Figueira, G., Mousseau, V. & Roy, B. 2007. Multiple criteria districting problems,
models, algorithms, and applications: The public transportation Paris region pricing system. Annals
of Operations Research 154(1): 69-92.
Thoreson, G. D. & Littschwa Vickrey W. 1961. On the preventions of gerrymandering. Political Science
Quarterly, 76(1): 105-110.
Zoltners, A. 1979. A unified approach to sales territory alignment. Sales Management: New Developments
from Behavioral and Decision Model Research, Marketing Science Institute, Cambridge, MA: 360-
Yamada, T. 2009. A mini-max spanning forest approach to the political districting problem. International
Journal of Systems Science. 40: 471-477.
