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

References

• Adler WT, Wang SSH (2019) Response to Cho and Liu, “Sampling from complicated and unknown distributions: Monte Carlo and Markov chain Monte Carlo methods for redistricting”. Phys. A Statist. Mech. Appl. 516:591–593.Crossref, Google Scholar
• Altman M (1997) The computational complexity of automated redistricting: Is automation the answer? Rutgers Comput. Tech. Law J. 23:81.Google Scholar
• Ancheta AN (2007) Language accommodation and the Voting Rights Act. Henderson A, ed. Voting Rights Act Reauthorization Of 2006: Perspectives on Democracy, Participation, and Power (University of California Regents School, Berkeley), 293–325.Google Scholar
• Arredondo V, Martínez-Panero M, Peña T, Ricca F (2021) Mathematical political districting taking care of minority groups. Ann. Oper. Res. 305(1–2):375–402.Crossref, Google Scholar
• Autry EA, Carter D, Herschlag GJ, Hunter Z, Mattingly JC (2021) Metropolized multiscale forest recombination for redistricting. Multiscale Modeling Simulations 19(4):1885–1914.Crossref, Google Scholar
• Bandle C (2017) Dido’s problem and its impact on modern mathematics. Notices AMS 64(9):980–984.Google Scholar
• Bar-Natan A, Najt L, Schutzman Z (2020) The Gerrymandering jumble: Map projections permute districts’ compactness scores. Cartography Geographic Inform. Sci. 47(4):321–335.Crossref, Google Scholar
• Barnes R, Solomon J (2021) Gerrymandering and compactness: Implementation flexibility and abuse. Political Anal. 29(4):448–466.Crossref, Google Scholar
• Becker A, Solomon J (2022) Redistricting algorithms. Duchin M, Walch O, eds. Political Geometry (Birkhauser, Basel, Switzerland), 303–340.Crossref, Google Scholar
• Becker A, Duchin M, Gold D, Hirsch S (2021) Computational redistricting and the Voting Rights Act. Election Law J. Rules Politics Policy 20(4):407–441.Crossref, Google Scholar
• Belotti P, Kirches C, Leyffer S, Linderoth J, Luedtke J, Mahajan A (2013) Mixed-integer nonlinear optimization. Acta Numerica 22:1–131.Crossref, Google Scholar
• Benson HY, Sağlam Ü (2013) Mixed-integer second-order cone programming: A survey. INFORMS TutORials Oper. Res. 13–36. Google Scholar
• Birge JR (1983) Redistricting to maximize the preservation of political boundaries. Soc. Sci. Res. 12(3):205–214.Crossref, Google Scholar
• Buchanan A (2023) Using optimization to support minority representation in Voting Rights Act Cases. OR/MS Today 50(46):32–35.Google Scholar
• Buchanan A, Sung JS, Butenko S, Pasiliao EL (2015) An integer programming approach for fault-tolerant connected dominating sets. INFORMS J. Comput. 27(1):178–188.Link, Google Scholar
• Cannon S, Duchin M, Randall D, Rule P (2022) Spanning tree methods for sampling graph partitions. Preprint, submitted October 4, https://arxiv.org/abs/2210.01401.Google Scholar
• Cannon S, Goldbloom-Helzner A, Gupta V, Matthews J, Suwal B (2023) Voting rights, Markov chains, and optimization by short bursts. Methodological Comput. Appl. Probab. 25(1):36.Crossref, Google Scholar
• Caro F, Shirabe T, Guignard M, Weintraub A (2004) School redistricting: Embedding GIS tools with integer programming. J. Oper. Res. Soc. 55(8):836–849.Crossref, Google Scholar
• Carvajal R, Constantino M, Goycoolea M, Vielma JP, Weintraub A (2013) Imposing connectivity constraints in forest planning models. Oper. Res. 61(4):824–836.Link, Google Scholar
• Chen J, Stephanopoulos NO (2021) The race-blind future of voting rights. Yale Law J. 130:862–947.Google Scholar
• Chikina M, Frieze A, Pegden W (2017) Assessing significance in a Markov chain without mixing. Proc. Natl. Acad. Sci. USA 114(11):2860–2864.Crossref, Google Scholar
• Cho WKT, Liu YY (2018) Sampling from complicated and unknown distributions: Monte Carlo and Markov chain Monte Carlo methods for redistricting. Phys. A Statist. Mech. Appl. 506:170–178.Crossref, Google Scholar
• Clelland J, Colgate H, DeFord D, Malmskog B, Sancier-Barbosa F (2022) Colorado in context: Congressional redistricting and competing fairness criteria in Colorado. J. Comput. Soc. Sci. 5(1):189–226.Crossref, Google Scholar
• Clelland JN, Bossenbroek N, Heckmaster T, Nelson A, Rock P, VanAusdall J (2021) Compactness statistics for spanning tree recombination. Preprint, submitted March 3, https://arxiv.org/abs/2103.02699.Google Scholar
• Cova TJ, Church RL (2000) Contiguity constraints for single-region site search problems. Geographical Anal. (Oxford) 32(4):306–329.Crossref, Google Scholar
• Cox E (1927) A method of assigning numerical and percentage values to the degree of roundness of sand grains. J. Paleontology 1(3):179–183.Google Scholar
• Davis M, Strigari F, Underhill W, Wice JM, Zamarripa C (2019) Redistricting Law 2020 (NCSL, Denver, CO).Google Scholar
• DeFord D, Duchin M (2022) Random walks and the universe of districting plans. Duchin M, Walch O, eds. Political Geometry (Birkhauser, Basel, Switzerland), 341–381.Crossref, Google Scholar
• DeFord D, Becker A, Gold D (2022) Brief of Computational Redistricting Experts as Amici Curiae in support of Appellees and Respondents in Merrill v. Milligan and Merrill v. Caster.Google Scholar
• DeFord D, Duchin M, Solomon J (2018) Comparison of districting plans for the Virginia House of Delegates. Technical report, Metric Geometry and Gerrymandering Group, Brooks.Google Scholar
• DeFord D, Duchin M, Solomon J (2021) Recombination: A family of Markov chains for redistricting. Harvard Data Sci. Rev. 3(1).Google Scholar
• DeFord D, Kimsey E, Zerr R (2023) Multi-balanced redistricting. J. Comput. Soc. Sci. 6(2):923–941.Crossref, Google Scholar
• DRA (2023) Dave’s redistricting. Accessed April 18, 2025, https://davesredistricting.org/.Google Scholar
• Drewes S (2009) Mixed integer second order cone programming. PhD thesis, TU Darmstadt, Darmstadt, Germany.Google Scholar
• Duchin M (2018) Outlier analysis for Pennsylvania congressional redistricting. LWV vs. Commonwealth of Pennsylvania Docket No. 159 MM 2017.Google Scholar
• Duchin M (2021) Presentation of alternative congressional districting plans for Alabama. Accessed April 18, 2025, https://www.supremecourt.gov/DocketPDF/21/21-1086/221826/20220425150837756_42140%20pdf%20Bowdre%20IV%20Supplemental%20JA.pdf.Google Scholar
• Duchin M (2022) Explainer: Compactness, by the numbers. Duchin M, Walch O, eds. Political Geometry (Birkhauser, Basel, Switzerland), 29–35.Crossref, Google Scholar
• Duchin M, Spencer D (2021) Models, race, and the law. Yale Law J. Forum 130:744–797.Google Scholar
• Duchin M, Walch O (2022) Interview: Drawing for the courts. Duchin M, Walch O, eds. Political Geometry (Birkhauser, Basel, Switzerland), 409–414.Crossref, Google Scholar
• Dyer ME, Frieze AM (1985) On the complexity of partitioning graphs into connected subgraphs. Discrete Appl. Math. 10(2):139–153.Crossref, Google Scholar
• Faenza Y, Kaibel V (2009) Extended formulations for packing and partitioning orbitopes. Math. Oper. Res. 34(3):686–697.Link, Google Scholar
• Fifield B, Higgins M, Imai K, Tarr A (2015) A new automated redistricting simulator using Markov chain Monte Carlo. Working paper, Princeton University, Princeton, NJ.Google Scholar
• Fischetti M, Leitner M, Ljubić I, Luipersbeck M, Monaci M, Resch M, Salvagnin D, et al. (2017) Thinning out Steiner trees: A node-based model for uniform edge costs. Math. Programming Comput. 9(2):203–229.Crossref, Google Scholar
• Fravel J, Hildebrand R, Goedert N, Travis L, Pierson M (2024) Optimizing representation in redistricting: Dual bounds for partitioning problems with non-convex objectives. Preprint, submitted May 26, https://arxiv.org/abs/2305.17298v2.Google Scholar
• Freeman N (2014) Nobody lives here: The nearly 5 million census blocks with zero population. Accessed April 18, 2025, https://tumblr.mapsbynik.com/post/82791188950/nobody-lives-here-the-nearly-5-million-census.Google Scholar
• Garfinkel RS, Nemhauser GL (1970) Optimal political districting by implicit enumeration techniques. Management Sci. 16(8):B–495.Google Scholar
• Gordon A, Spencer DM (2022) Explainer: A brief introduction to the Voting Rights Act. Political Geometry: Rethinking Redistricting in the US with Math, Law, and Everything in Between (Birkhauser, Basel, Switzerland), 131–136.Crossref, Google Scholar
• Grofman B (1982) For single member districts random is not equal. Representation and Redistricting Issues (Lexington Books, Lanham, MD), 55–58.Google Scholar
• Grofman B, Handley L, Lublin D (2001) Drawing effective minority districts: A conceptual framework and some empirical evidence. North Carolina Law Rev. 79:1383.Google Scholar
• Gurnee W, Shmoys DB (2021) Fairmandering: A column generation heuristic for fairness-optimized political districting. Proc. SIAM Conf. Appl. Comput. Discrete Algorithms (SIAM, Philadelphia), 88–99.Crossref, Google Scholar
• Hebert JG, Vandenberg ME, Smith P (2010) The Realist’s Guide to Redistricting: Avoiding the Legal Pitfalls (American Bar Association, Chicago, IL).Google Scholar
• Henzinger A, Noe A, Schulz C (2020) ILP-based local search for graph partitioning. ACM J. Experiment. Algorithmics 25:1–26.Crossref, Google Scholar
• Hess S, Weaver J, Siegfeldt H, Whelan J, Zitlau P (1965) Nonpartisan political redistricting by computer. Oper. Res. 13(6):998–1006.Link, Google Scholar
• Hofeller TB (2015) Declaration of Thomas Brooks Hofeller. Accessed April 18, 2025, https://www.supremecourt.gov/DocketPDF/18/18-281/77913/20190102174617179_Vol%204%20Part%201.pdf.Google Scholar
• Hojati M (1996) Optimal political districting. Comput. Oper. Res. 23(12):1147–1161.Crossref, Google Scholar
• Laney GP (2008) The Voting Rights Act of 1965, as amended: Its history and current issues. Accessed April 18, 2025, https://congressionalresearch.com/95-896/document.php.Google Scholar
• Lublin D, Handley L, Brunell TL, Grofman B (2020) Minority success in non-majority minority districts: Finding the “sweet spot. J. Race. Ethnicity. Politics 5(2):275–298.Crossref, Google Scholar
• McCartan C (2023) Finding Pareto efficient redistricting plans with short bursts. Preprint, submitted April 2, https://arxiv.org/abs/2304.00427.Google Scholar
• McCartan C, Imai K (2023) Sequential Monte Carlo for sampling balanced and compact redistricting plans. Ann. Appl. Statist. 17(4):3300–3323.Crossref, Google Scholar
• McCartan C, Kenny CT, Simko T, Garcia IIG, Wang K, Wu M, Kuriwaki S, et al. (2022b) Simulated redistricting plans for the analysis and evaluation of redistricting in the US. Sci. Data 9(1):689.Crossref, Google Scholar
• McCartan C, Kenny C, Simko T, Kuriwaki S, Garcia IIG, Wang K, Wu M, et al. (2022a) ALARM project. Accessed April 18, 2025, https://alarm-redist.github.io/fifty-states/.Google Scholar
• McDonald M (2019) The predominance test: A judicially manageable compactness standard for redistricting. Yale Law J. Forum 129:18.Google Scholar
• Mehrotra A, Johnson EL, Nemhauser GL (1998) An optimization based heuristic for political districting. Management Sci. 44(8):1100–1114.Link, Google Scholar
• MGGG (2024a) Gerrychain v0.3.2. Accessed April 18, 2025, https://gerrychain.readthedocs.io/en/latest/.Google Scholar
• MGGG (2024b) Region-Aware ReCom. Accessed April 18, 2025, https://gerrychain.readthedocs.io/en/latest/user/recom/#region-aware-recom.Google Scholar
• MGGG (2024c) Using Gingleator. Accessed April 18, 2025, https://gerrychain.readthedocs.io/en/latest/user/optimizers/#using-gingleator.Google Scholar
• Niemi RG, Grofman B, Carlucci C, Hofeller T (1990) Measuring compactness and the role of a compactness standard in a test for partisan and racial Gerrymandering. J. Politics 52(4):1155–1181.Crossref, Google Scholar
• Oehrlein J, Haunert JH (2017) A cutting-plane method for contiguity-constrained spatial aggregation. J. Spatial Inform. Sci. 2017(15):89–120.Google Scholar
• Önal H, Patrick KT (2016) A mathematical programming approach to political redistricting with compactness and community integrity considerations. Technical report, University of Illinois Urbana-Champaign, Urbana-Champaign.Google Scholar
• Osserman R (1978) The isoperimetric inequality. Bull. Amer. Math. Soc. 84(6):1182–1238.Crossref, Google Scholar
• Persily N (2004) When judges carve democracies: A primer on court-drawn redistricting plans. George Washington Law Rev. 73:1131.Google Scholar
• Polsby DD, Popper RD (1991) The third criterion: Compactness as a procedural safeguard against partisan Gerrymandering. Yale Law Policy Rev. 9:301.Google Scholar
• Princeton Gerrymandering Project (2023) Redistricting report card. Accessed April 18, 2025, https://gerrymander.princeton.edu/redistricting-report-card/.Google Scholar
• Procaccia AD, Tucker-Foltz J (2022) Compact redistricting plans have many spanning trees. Naor S, Buchbinder N, eds. Proc. Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 3754–3771.Google Scholar
• Redensky Y, Leaverton C (2023) Ongoing Voting Rights Act redistricting litigation after SCOTUS ruling in Allen v. Milligan. Accessed April 18, 2025, https://www.brennancenter.org/our-work/research-reports/ongoing-voting-rights-act-redistricting-litigation-after-scotus-ruling.Google Scholar
• Redistricting Data Hub (2021) Download data. Accessed April 18, 2025, https://redistrictingdatahub.org/data/.Google Scholar
• Ricca F, Scozzari A, Simeone B (2013) Political districting: From classical models to recent approaches. Ann. Oper. Res. 204(1):271–299.Crossref, Google Scholar
• Schutzman Z (2020) Trade-offs in fair redistricting. Proc. AAAI/ACM Conf. AI, Ethics, Soc. (ACM, New York), 159–165.Google Scholar
• Schwartzberg JE (1965) Reapportionment, Gerrymanders, and the notion of compactness. Minnesota Law Rev. 50:443.Google Scholar
• Shahmizad M, Buchanan A (2025) Political districting to minimize county splits. Oper. Res. 73(2):752–774.Google Scholar
• Shirabe T (2005) A model of contiguity for spatial unit allocation. Geographical Anal. (Oxford) 37(1):2–16.Crossref, Google Scholar
• Shirabe T (2009) Districting modeling with exact contiguity constraints. Environment. Planning B Planning Design 36(6):1053–1066.Crossref, Google Scholar
• Smith EM, Pantelides CC (1999) A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chemical Engrg. 23(4–5):457–478.Crossref, Google Scholar
• Swamy R, King DM, Jacobson SH (2023) Multiobjective optimization for politically fair districting: A scalable multilevel approach. Oper. Res. 71(2):536–562.Link, Google Scholar
• Temiz N, Trapp A, Prokopyev OA, Camacho CJ (2010) Optimization of minimum set of protein–DNA interactions: A quasi exact solution with minimum over-fitting. Bioinformatics 26(3):319–325.Crossref, Google Scholar
• U.S. Census Bureau (2021a) Decennial Census P.L. 94-171 redistricting data. Accessed April 18, 2025, https://www.census.gov/programs-surveys/decennial-census/about/rdo/summary-files.html.Google Scholar
• U.S. Census Bureau (2021b) TIGER/line shapefiles. Accessed April 18, 2025, https://www.census.gov/geographies/mapping-files/time-series/geo/tiger-line-file.html.Google Scholar
• U.S. Census Bureau (2022) State legislative districts. Accessed April 18, 2025, https://www.census.gov/programs-surveys/decennial-census/about/rdo/state-legislative-district.html.Google Scholar
• U.S. Department of Justice (2021) Guidance under Section 2 of the Voting Rights Act, 52 U.S.C. 10301, for redistricting and methods of electing government bodies. Accessed April 18, 2025, https://www.justice.gov/opa/press-release/file/1429486/download.Google Scholar
• Validi H, Buchanan A (2022) Political districting to minimize cut edges. Math. Programming Comput. 14(4):623–672.Crossref, Google Scholar
• Validi H, Buchanan A, Lykhovyd E (2022) Imposing contiguity constraints in political districting models. Oper. Res. 70(2):867–892.Link, Google Scholar
• Vickrey W (1961) On the prevention of Gerrymandering. Political Sci. Quart. 76(1):105–110.Crossref, Google Scholar
• Wang Y, Buchanan A, Butenko S (2017) On imposing connectivity constraints in integer programs. Math. Programming 166(1–2):241–271.Crossref, Google Scholar
• Weaver JB, Hess SW (1963) A procedure for nonpartisan districting: Development of computer techniques. Yale Law J. 73:288.Crossref, Google Scholar
• Young HP (1988) Measuring the compactness of legislative districts. Legislative Stud. Quart. 13(1):105–115.Crossref, Google Scholar
• Zhang J, Validi H, Buchanan A, Hicks IV (2024) Linear-size formulations for connected planar graph partitioning and political districting. Optim. Lett. 18:19–31.Crossref, Google Scholar
• Zoltners AA, Sinha P (1983) Sales territory alignment: A review and model. Management Sci. 29(11):1237–1256.Link, Google Scholar