Enabling Redistricting Reform: A Computational Study of Zoning Optimization
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 have developed 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. Experimental results demonstrate desirable effectiveness and scalability of our approach—up to 131,000 processors—for solving large redistricting problems, which enables substantive research into the relationship between democratic ideals and phenomena such as gerrymandering. Our early research has been well-received on both the technical and substantive fronts. We intend now to further enhance the efficiency of the optimization algorithm as well as to utilize our computational tool to embark on a focused analysis of how best to institute redistricting reform in the United States.