Political Districting to Optimize the Polsby-Popper Compactness Score with Application to Voting Rights
- 1 September 2025
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (5) , 2330-2350
Abstract
When drawing political districts, important criteria include district compactness and the ability of minority groups to convert votes into seats. In litigation, compactness is usually measured via the Polsby-Popper score; however, this score has largely been absent from the operations research literature, presumably because of its nonlinear nature. In “Political Districting to Optimize the Polsby-Popper Compactness Score with Application to Voting Rights,” Belotti, Buchanan, and Ezazipour propose new mixed-integer second-order cone programs (MISOCPs) to optimize this score, enabling them to find optimally compact districts built from voting precincts. The methods are extended to find compact plans with many majority-minority districts. This is the task faced by plaintiffs in lawsuits brought under the Voting Rights Act of 1965 who must show that an alternative plan exists in which the minority group could achieve better representation. Computational experiments show that the MISCOP-based methods perform as well (or better) than state-of-the-art approaches for this task, scaling to instances with nearly 200,000 census blocks.Keywords
This publication has 49 references indexed in Scilit:
- Linear-size formulations for connected planar graph partitioning and political districtingOptimization Letters, 2023
- Voting Rights, Markov Chains, and Optimization by Short BurstsMethodology and Computing in Applied Probability, 2023
- Interview: Drawing for the courts2022
- Explainer: Compactness, by the numbers2022
- Explainer: A brief introduction to the Voting Rights Act2022
- Redistricting algorithms2022
- Random walks and the universe of districting plans2022
- Mathematical political districting taking care of minority groupsAnnals of Operations Research, 2021
- On imposing connectivity constraints in integer programsMathematical Programming, 2017
- Political Districting: from classical models to recent approachesAnnals of Operations Research, 2013