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 language | English |
|---|---|
| Pages (from-to) | 78-92 |
| Number of pages | 15 |
| Journal | Swarm and Evolutionary Computation |
| Volume | 30 |
| DOIs | |
| State | Published - Oct 1 2016 |
| Externally published | Yes |
Funding
This material is based in part upon work supported by the National Science Foundation (NSF) under Grant 1047916 . Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not reflect the views of NSF. Computational experiments in this research used the Blue Waters sustained-petascale computing resources, which is supported by the NSF (Grants OCI-0725070 and ACI-1238993 ) and the state of Illinois. Blue Waters is a joint effort of the University of Illinois at Urbana-Champaign and its National Center for Supercomputing Applications. The performance study used the ROGER supercomputer at the University of Illinois , which is supported by NSF (Grant 1429699 ). The authors also acknowledge the Texas Advanced Computing Center (TACC) at the University of Texas at Austin for providing HPC resources via the Stampede supercomputer that have also contributed to our research results.
Keywords
- Combinatorial optimization
- Evolutionary algorithm
- Heuristics
- High-performance parallel computing
- Redistricting
- Spatial optimization