CAREER: Parsimonious Models for Redistricting

Oklahoma State University, Stillwater OK

Investigators

Abstract

This Faculty Early Career Development (CAREER) grant promotes the national welfare by supporting scientific research into improved methods for redistricting. Common criticisms of districting plans include unequal district populations, a lack of contiguity or compactness, the needless splitting of counties (or other political subdivisions), or the use of demographic characteristics of the population to ensure anomalous representation. The challenge of neutrally designing districting plans leads to many questions about baselines and tradeoffs. This project addresses these challenges through optimization methods that provide a mathematically sound, transparent approach. Current optimization formulations lead to very large problems that cannot be solved using existing methods. This research will: (i) investigate methods for establishing the limits of what is possible in a redistricting plan, and (ii) provide politically neutral methods that can inform the public about how well various constraints can restrain manipulation. The three components of the education plan will serve to excite students about a career in operations research. The PI will engage and mentor graduate and undergraduate students in the research. Students from underrepresented populations will actively be sought to work on the project, in part, through collaboration with the Oklahoma Louis Stokes Alliance for Minority Participation. Existing exact models for redistricting do not scale well. Even the best of them begin to struggle on county-level instances of redistricting due, in part, to the large number of variables defining these models. To satisfy critical population-equality constraints requires a finer level of granularity, which results in an even larger problem. This research considers new models and algorithms that have the potential to handle significantly larger instances. This is enabled, in part, by the newly researched Arborescence Models, which exploit planar graph duality to simultaneously achieve small size and remarkable strength. Some of the researched techniques for handling contiguity and compactness constraints, e.g., length-bounded cuts, are new and require few or no additional variables. These methods go well beyond the many existing approaches based on multi-commodity flows or layered graphs. Investigation of these methods have the potential to enable new solutions to network problems that have distance, latency, and compactness constraints. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.