We consider a fundamental question in political districting: How many counties can be kept whole (i.e., not split across multiple districts), while satisfying basic criteria like contiguity and population balance? To answer this question, we propose integer programming techniques based on combinatorial Benders decomposition. The main problem decides which counties to keep whole, and the subproblem coarsens the selected counties and then seeks a feasible plan. We apply the approach to all congressional and legislative instances across the USA, generating plans that are provably optimal. Finally, we conduct a case study for Tennessee’s state house districts and find that the plaintiffs’ case in Wygant v. Lee could have been even stronger if our optimization methods had assisted in the drawing of demonstration plans. Our code and results are available on GitHub.
Citation
Submitted to a journal