\(\)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 \pi 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 with optimum Polsby-Popper score. Specifically, we propose new mixed-integer second-order cone programs (MISOCPs), which can be solved with existing optimization software. We investigate their tractability by applying them to real-life districting instances in the USA. Experiments show that they are able to: (i) identify the most compact majority-minority districts at the tract level; (ii) identify the most compact districting plans at the county level; and (iii) refine existing tract-level plans to make them substantially more compact. Our techniques could be used by plaintiffs when seeking to overturn maps that dilute the voting strength of minority groups. Our python code and results are publicly available on GitHub.
Submitted to a journal