*Result*: Political Districting to Optimize the Polsby-Popper Compactness Score with Application to Voting Rights.

*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. 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)/P2. 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. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)*

*Full text is not displayed to guests* *Login for full access*