Abstract

Political redistricting, a well-known problem in political science and geographic information science, can be formulated as a combinatorial optimization problem, with objectives and constraints defined to meet legal requirements. The formulated optimization problem is NP-hard. We develop a scalable evolutionary computational approach utilizing massively parallel high performance computing for political redistricting optimization and analysis at fine levels of granularity. Our computational approach is based in strong substantive knowledge and deep adherence to Supreme Court mandates. Since the spatial configuration plays a critical role in the effectiveness and numerical efficiency of redistricting algorithms, we have designed spatial evolutionary algorithm (EA) operators that incorporate spatial characteristics and effectively search the solution space. Our parallelization of the algorithm further harnesses massive parallel computing power provided by supercomputers via the coupling of EA search processes and a highly scalable message passing model that maximizes the overlapping of computing and communication at runtime. Experimental results demonstrate desirable effectiveness and scalability of our approach (up to 131K processors) for solving large redistricting problems, which enables substantive research into the relationship between democratic ideals and phenomena such as partisan gerrymandering.

Original languageEnglish (US)
Pages (from-to)78-92
Number of pages15
JournalSwarm and Evolutionary Computation
Volume30
DOIs
StatePublished - Oct 1 2016

Keywords

  • Combinatorial optimization
  • Evolutionary algorithm
  • Heuristics
  • High-performance parallel computing
  • Redistricting
  • Spatial optimization

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'PEAR: a massively parallel evolutionary computation approach for political redistricting optimization and analysis'. Together they form a unique fingerprint.

Cite this