Imposing Contiguity Constraints in Political Districting Models

References

• Adler WT, Wang SS-H (2019) Response to Cho and Liu, “Sampling from complicated and unknown distributions: Monte Carlo and Markov chain Monte Carlo methods for redistricting. Phys. A 516:591–593.Crossref, Google Scholar
• Ahn N, Park S (2015) An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks. Wireless Networks 21(3):783–792.Crossref, Google Scholar
• Altman M (1997) The computational complexity of automated redistricting: Is automation the answer? Rutgers Comput. Technol. Law J. 23:81.Google Scholar
• Altman M (1998) Traditional districting principles: Judicial myths vs. reality. Soc. Sci. History 22(2):159–200.Crossref, Google Scholar
• Altman M, McDonald M (2010) The promise and perils of computers in redistricting. Duke J. Constitutional Law Public Policy 5:69–111.Google Scholar
• Altman M, McDonald MP (2011) BARD: Better automated redistricting. J. Statist. Software 42(4):1–28.Crossref, Google Scholar
• Altman M, McDonald M (2018) Redistricting by formula: An Ohio reform experiment. Amer. Political Res. 46(1):103–131.Crossref, Google Scholar
• Álvarez-Miranda E, Sinnl M (2017) A relax-and-cut framework for large-scale maximum weight connected subgraph problems. Comput. Oper. Res. 87:63–82.Crossref, Google Scholar
• Álvarez-Miranda E, Ljubić I, Mutzel P (2013a) The maximum weight connected subgraph problem. Facets of Combinatorial Optimization (Springer, Berlin), 245–270.Crossref, Google Scholar
• Álvarez-Miranda E, Ljubić I, Mutzel P (2013b) The rooted maximum node-weight connected subgraph problem. Proc. Internat. Conf. AI OR Techniques Constriant Programming Combinatorial Optim. Problems (Springer, Berlin), 300–315.Google Scholar
• Applegate D (2019) South Carolina districting, July 16.Google Scholar
• Arrington TS (2010) Redistricting in the US: A review of scholarship and plan for future research. Forum 8(2). https://www.degruyter.com/document/doi/10.2202/1540-8884.1351/html.Google Scholar
• Arslan O, Jabali O, Laporte G (2020) A flexible, natural formulation for the network design problem with vulnerability constraints. INFORMS J. Comput. 32(1):120–134.Link, Google Scholar
• Arslan O, Karaşan OE, Mahjoub AR, Yaman H (2019) A branch-and-cut algorithm for the alternative fuel refueling station location problem with routing. Transportation Sci. 53(4):1107–1125.Link, Google Scholar
• Beasley JE (1993) Lagrangean heuristics for location problems. Eur. J. Oper. Res. 65(3):383–399.Crossref, Google Scholar
• Boehm E (2018) Gerrymandering is out of control. Reason, March 27, https://reason.com/archives/2018/03/27/gerrymandering-is-out-of-control.Google Scholar
• Bozkaya B, Erkut E, Laporte G (2003) A tabu search heuristic and adaptive memory procedure for political districting. Eur. J. Oper. Res. 144(1):12–26.Crossref, Google Scholar
• Briant O, Naddef D (2004) The optimal diversity management problem. Oper. Res. 52(4):515–526.Link, Google Scholar
• Buchanan A (2019) Districting, July 29.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
• Bullock CS III (2010) Redistricting: The Most Political Activity in America (Rowman & Littlefield Publishers).Google Scholar
• Bureau of the Census (2012) TIGER/Line shapefiles. Accessed January 23, 2019, https://www2.census.gov/geo/tiger/TIGER2010DP1/Profile-County_Tract.zip.Google Scholar
• Bureau of the Census (2018) Census tracts for the 2020 census: Final criteria. Federal Register 83(219):56277–56284.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
• Cho WKT, Liu YY (2018) Sampling from complicated and unknown distributions: Monte Carlo and Markov chain Monte Carlo methods for redistricting. Phys. A 506:170–178.Crossref, Google Scholar
• Cohen-Addad V, Klein PN, Young NE (2018) Balanced centroidal power diagrams for redistricting. Proc. 26th ACM SIGSPATIAL Internat. Conf. Adv. Geographic Inform. Systems (ACM), 389–396.Google Scholar
• Daskin MS, Tucker EL (2018) The trade-off between the median and range of assigned demand in facility location models. Internat. J. Production Res. 56(1-2):97–119.Crossref, Google Scholar
• DeFord D, Duchin M, Solomon J (2021) Recombination: A family of Markov chains for redistricting. Harvard Data Sci. Rev. 3(1). https://hdsr.mitpress.mit.edu/pub/1ds8ptxu/release/4?readingCollection=a133a0a2.Google Scholar
• Di Cortona PG, Manzi C, Pennisi A, Ricca F, Simeone B (1999) Evaluation and Optimization of Electoral Systems, vol. 1 of Monographs on Discrete Mathematics and Applications (SIAM, Philadelphia).Crossref, Google Scholar
• Drexl A, Haase K (1999) Fast approximation methods for sales force deployment. Management Sci. 45(10):1307–1323.Link, Google Scholar
• Duchin M (2018) Political geometry: voting districts, “compactness,” and ideas about fairness. MAA-AMS-SIAM Gerald and Judith Porter Public Lecture given at the 2018 Joint Mathematics Meetings. Video of talk available at https://www.youtube.com/watch?v=VddLOevo7QY.Google Scholar
• Duchin M (2020) Dealing with non-contiguous tracts, January 8.Google Scholar
• Duchin M, Gladkova T, Henninger-Voss E, Ben Klingensmith HN, Wheelen H (2019) Locating the representational baseline: Republicans in Massachusetts. Election Law J. Rules Political Policy 18(4):388–401.Google Scholar
• Duque JC, Church RL, Middleton RS (2011) The p-regions problem. Geographic Anal. 43(1):104–126.Crossref, 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
• Ford LR Jr, Fulkerson DR (1962) Flows in Networks (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Gamrath G, Koch T, Maher SJ, Rehfeldt D, Shinano Y (2017) SCIP-Jack: A solver for STP and variants with parallelization extensions. Math. Programming Comput. 9(2):231–296.Crossref, Google Scholar
• Garfinkel RS, Nemhauser GL (1970) Optimal political districting by implicit enumeration techniques. Management Sci. 16(8):B–495.Link, Google Scholar
• Gentry S, Chow E, Massie A, Segev D (2015) Gerrymandering for justice: Redistricting US liver allocation. Interfaces 45(5):462–480.Link, Google Scholar
• Goderbauer S, Winandy J (2018) Political districting problem: Literature review and discussion with regard to federal elections in Germany. Working paper, RWTH Aachen University, Aachen, Germany.Google Scholar
• Gopalan R, Kimbrough SO, Murphy FH, Quintus N (2013) The Philadelphia districting contest: Designing territories for city council based upon the 2010 census. Interfaces 43(5):477–489.Link, Google Scholar
• Grofman B (1985) Criteria for districting: A social science perspective. UCLA Law Rev. 33:77.Google Scholar
• Guo D, Jin H (2011) iRedistrict: Geovisual analytics for redistricting optimization. J. Visual Language Comput. 22(4):279–289.Crossref, Google Scholar
• Gurobi (2017) Gurobi guidelines for numerical issues. Accessed January 9, 2020, http://files.gurobi.com/Numerics.pdf.Google Scholar
• Gutiérrez-Andrade MÁ, Rincón-García EA, de-los Cobos-Silva SG, Lara-Velázquez P, Mora-Gutiérrez RA, Ponsich A (2019) Simulated annealing and artificial bee colony for the redistricting process in Mexico. INFORMS J. Appl. Analytics 49(3):189–200.Link, Google Scholar
• Haase K, Müller S (2014) Upper and lower bounds for the sales force deployment problem with explicit contiguity constraints. Eur. J. Oper. Res. 237(2):677–689.Crossref, Google Scholar
• Hebert GJ, Vandenberg ME, Smith P (2010) The Realist’s Guide to Redistricting: Avoiding the Legal Pitfalls (American Bar Association).Google Scholar
• Henzinger MR, Klein P, Rao S, Subramanian S (1997) Faster shortest-path algorithms for planar graphs. J. Comput. System Sci. 55(1):3–23.Crossref, Google Scholar
• Hess SW, Weaver JB, Siegfeldt HJ, Whelan JN, Zitlau PA (1965) Nonpartisan political redistricting by computer. Oper. Res. 13(6):998–1006.Link, Google Scholar
• Hojati M (1996) Optimal political districting. Comput. Oper. Res. 23(12):1147–1161.Crossref, Google Scholar
• IOGP (2019) EPSG data set. Accessed January 23, 2019, http://www.epsg.org/.Google Scholar
• Kaplan H, Nussbaum Y (2011) Maximum flow in directed planar graphs with vertex capacities. Algorithmica 61(1):174–189.Crossref, Google Scholar
• Kappel F, Kuntsevich AV (2000) An implementation of Shor’s r-algorithm. Comput. Optim. Appl. 15(2):193–205.Crossref, Google Scholar
• Kim MJ (2019) Give-and-take heuristic model to political redistricting problems. Spatial Inform. Res. 27:539–552.Crossref, Google Scholar
• Kim M, Xiao N (2017) Contiguity-based optimization models for political redistricting problems. Internat. J. Appl. Geospatial Res. 8(4):1–18.Crossref, Google Scholar
• King DM, Jacobson SH, Sewell EC (2015) Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning. Math. Programming 149(1-2):425–457.Crossref, Google Scholar
• King DM, Jacobson SH, Sewell EC (2018) The geo-graph in practice: Creating United States congressional districts from census blocks. Comput. Optim. Appl. 69(1):25–49.Crossref, Google Scholar
• King DM, Jacobson SH, Sewell EC, Cho WKT (2012) Geo-graphs: An efficient model for enforcing contiguity and hole constraints in planar graph partitioning. Oper. Res. 60(5):1213–1228.Link, Google Scholar
• Kong Y, Zhu Y, Wang Y (2019) A center-based modeling approach to solve the districting problem. Internat. J. Geographic Inform. Sci. 33(2):368–384.Crossref, Google Scholar
• Lacki J, Nussbaum Y, Sankowski P, Wulff-Nilsen C (2012) Single source: All sinks max flows in planar digraphs. Proc. IEEE 53rd Annual Sympos. on Foundations of Computer Science (IEEE, New York), 599–608.Google Scholar
• Levin HA, Friedler SA (2019) Automated congressional redistricting. J. Experiment. Algorithmics 24(1):1–10.Crossref, Google Scholar
• Linskey A (2012) Foes of congressional map meet target. The Baltimore Sun, July 11, http://articles.baltimoresun.com/2012-07-11/news/bs-md-congressional-redistrict-20120711_1_congressional-map-new-map-state-board.Google Scholar
• Liu YY, Cho WKT, Wang S (2016) PEAR: A massively parallel evolutionary computation approach for political redistricting optimization and analysis. Swarm Evolution Comput. 30:78–92.Crossref, Google Scholar
• Lykhovyd E (2019) Efficient implementation of Shor’s r-algorithm using MKL. Accessed January 9, 2020, https://github.com/zhelih/ralg.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
• Mikhalevich VS, Shor NZ, Galustuva LA, Zhurbenko NG, Momot AI, Sibirko AN, Trubin VA, et al. (1977) Computational Methods of Choice of Optimal Design Decisions (Naukova Dumka).Google Scholar
• Miller S (2007) The Problem of Redistricting: The Use of Centroidal Voronoi Diagrams to Build Unbiased Congressional Districts (Whitman College).Google Scholar
• Murphy FH, Hess SW, Wong-Martinez CG (2013) Politics. Gass SI, Fu MC, eds. Encyclopedia of Operations Research and Management Science (Springer, Berlin), 1137–1141.Crossref, Google Scholar
• NCSL (2019) Redistricting criteria. Accessed June 20, 2019, http://www.ncsl.org/research/redistricting/redistricting-criteria.aspx.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 J-H (2017) A cutting-plane method for contiguity-constrained spatial aggregation. J. Spatial Inform. Sci. 2017(15):89–120.Google Scholar
• Olson B (2019) Impartial automatic redistricting. Accessed June 21, 2019, https://bdistricting.com/2010/.Google Scholar
• Rehfeldt D, Koch T (2019) Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem. SIAM J. Optim. 29(1):369–398.Crossref, Google Scholar
• Rehfeldt D, Koch T, Maher SJ (2019) Reduction techniques for the prize collecting Steiner tree problem and the maximum-weight connected subgraph problem. Networks 73(2):206–233.Crossref, Google Scholar
• Resende MGC, Werneck RF (2004) A hybrid heuristic for the p-median problem. J. Heuristics 10(1):59–88.Crossref, Google Scholar
• Ricca F, Simeone B (2008) Local search algorithms for political districting. Eur. J. Oper. Res. 189(3):1409–1426.Crossref, Google Scholar
• Ricca F, Scozzari A, Simeone B (2008) Weighted Voronoi region algorithms for political districting. Math. Comput. Modeling 48(9-10):1468–1477.Crossref, 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
• Salemi H, Buchanan A (2020) Parsimonious formulations for low-diameter clusters. Math. Programming Comput. 12(3):493–528.Crossref, Google Scholar
• Shirabe T (2005) A model of contiguity for spatial unit allocation. Geographic Anal. 37(1):2–16.Crossref, Google Scholar
• Shirabe T (2009) Districting modeling with exact contiguity constraints. Environmental Planning B: Planning Design 36(6):1053–1066.Crossref, Google Scholar
• Shor NZ (1985) Minimization Methods for Non-Differentiable Functions, vol. 3 of Springer Series in Computational Mathematics (Springer, Berlin).Crossref, Google Scholar
• Svec L, Burden S, Dilley A (2007) Applying Voronoi diagrams to the redistricting problem. UMAP J. 28(3):313–329.Google Scholar
• Swamy R, King DM, Jacobson SH (2019a) A case for transparency in the design of political districts. Working paper, University of Illinois at Urbana-Champaign, Urbana, Illinois.Google Scholar
• Swamy R, King DM, Jacobson SH (2019b) Multi-objective optimization for political districting: a scalable multilevel approach. Working paper.Google Scholar
• Validi H, Buchanan A (2019) A note on “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs.” Networks 73(1):135–142.Crossref, Google Scholar
• Validi H, Buchanan A (2020) The optimal design of low-latency virtual backbones. INFORMS J. Comput. 32(4):952–967.Abstract, 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
• Young PH (1988) Measuring the compactness of legislative districts. Legislative Stud. Quart. 13(1):105–115.Crossref, Google Scholar
• Zoltners AA, Sinha P (1983) Sales territory alignment: A review and model. Management Sci. 29(11):1237–1256.Link, Google Scholar