Political Districting to Optimize the Polsby-Popper Compactness Score with Application to Voting Rights

In the academic literature and in expert testimony, the Polsby-Popper score is the most popular way to measure the compactness of a political district. Given a district with area A and perimeter P , its Polsby-Popper score is given by ( 4 π A ) / P 2 . This score takes values between zero and one, with circular districts achieving a perfect score of one. In this paper, we propose the first mathematical optimization models to draw districts (or districting plans) with optimum Polsby-Popper score. Specifically, we propose new mixed-integer second-order cone programs (MISOCPs), which can be solved with existing optimization software. Experiments show that they can identify the most compact single districts at the precinct level and the most compact plans at the county level. Then, we turn to the problem of drawing compact plans with a large number of majority-minority districts. This is the task faced by plaintiffs in Voting Rights Act cases who must show that an alternative plan exists in which the minority group could achieve better representation, a legal hurdle known as the first Gingles precondition. For this task, we propose new MISOCP-based heuristics that often outperform enacted maps on standard criteria, sometimes by substantial margins. They also perform well against state-of-the-art heuristics like short bursts and can be used to polish maps with hundreds of thousands of census blocks. Our techniques could assist plaintiffs when seeking to overturn maps that dilute the voting strength of minority groups. Our code is available on GitHub.