The political districting of Kuwait: Heuristic approaches


  • SHAFIQAH ALAWADHI Department of Statistics and Operations Research, Faculty of Science, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait
  • RYM MAHALLA Department of Statistics and Operations Research, Faculty of Science, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait.


Combinatorial optimization, constraint propagation, heuristics, integer programming, multiple objective.


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.


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.