IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v60y2012i5p1213-1228.html
   My bibliography  Save this article

Geo-Graphs: An Efficient Model for Enforcing Contiguity and Hole Constraints in Planar Graph Partitioning

Author

Listed:
  • Douglas M. King

    (Department of Industrial and Enterprise Systems Engineering, University of Illinois, Urbana, Illinois 61801)

  • Sheldon H. Jacobson

    (Department of Computer Science, University of Illinois, Urbana, Illinois 61801)

  • Edward C. Sewell

    (Department of Mathematics and Statistics, Southern Illinois University Edwardsville, Edwardsville, Illinois 62026)

  • Wendy K. Tam Cho

    (Department of Political Science and Statistics, National Center for Supercomputing Applications, University of Illinois, Urbana, Illinois 61801)

Abstract

Political districting is an intractable problem with significant ramifications for political representation. Districts often are required to satisfy some legal constraints, but these typically are not very restrictive, allowing decision makers to influence the composition of these districts without violating relevant laws. For example, while districts must often comprise a single contiguous area, a vast collection of acceptable solutions (i.e., sets of districts) remains. Choosing the best set of districts from this collection can be treated as a (planar) graph partitioning problem. When districts must be contiguous, successfully solving this problem requires an efficient computational method for evaluating contiguity constraints; common methods for assessing contiguity can require significant computation as the problem size grows. This paper introduces the geo-graph , a new graph model that ameliorates the computational burdens associated with enforcing contiguity constraints in planar graph partitioning when each vertex corresponds to a particular region of the plane. Through planar graph duality, the geo-graph provides a scale-invariant method for enforcing contiguity constraints in local search. Furthermore, geo-graphs allow district holes (which typically are considered undesirable) to be rigorously and efficiently integrated into the partitioning process.

Suggested Citation

  • Douglas M. King & Sheldon H. Jacobson & Edward C. Sewell & Wendy K. Tam Cho, 2012. "Geo-Graphs: An Efficient Model for Enforcing Contiguity and Hole Constraints in Planar Graph Partitioning," Operations Research, INFORMS, vol. 60(5), pages 1213-1228, October.
    • Handle: RePEc:inm:oropre:v:60:y:2012:i:5:p:1213-1228
    DOI: 10.1287/opre.1120.1083
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1120.1083
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1120.1083?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. W. Macmillan, 2001. "Redistricting in a GIS environment: An optimisation algorithm using switching-points," Journal of Geographical Systems, Springer, vol. 3(2), pages 167-180, August.
    2. Pierre Hansen & Brigitte Jaumard & Christophe Meyer & Bruno Simeone & Valeria Doring, 2003. "Maximum Split Clustering Under Connectivity Constraints," Journal of Classification, Springer;The Classification Society, vol. 20(2), pages 143-180, September.
    3. Ricca, Federica & Simeone, Bruno, 2008. "Local search algorithms for political districting," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1409-1426, September.
    4. Burcin Bozkaya & Erhan Erkut & Dan Haight & Gilbert Laporte, 2011. "Designing New Electoral Districts for the City of Edmonton," Interfaces, INFORMS, vol. 41(6), pages 534-547, December.
    5. Bozkaya, Burcin & Erkut, Erhan & Laporte, Gilbert, 2003. "A tabu search heuristic and adaptive memory procedure for political districting," European Journal of Operational Research, Elsevier, vol. 144(1), pages 12-26, January.
    6. Fernando Tavares-Pereira & José Figueira & Vincent Mousseau & Bernard Roy, 2007. "Multiple criteria districting problems," Annals of Operations Research, Springer, vol. 154(1), pages 69-92, October.
    7. Andreas Drexl & Knut Haase, 1999. "Fast Approximation Methods for Sales Force Deployment," Management Science, INFORMS, vol. 45(10), pages 1307-1323, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Camacho-Collados, M. & Liberatore, F. & Angulo, J.M., 2015. "A multi-criteria Police Districting Problem for the efficient and effective design of patrol sector," European Journal of Operational Research, Elsevier, vol. 246(2), pages 674-684.
    2. Vangerven, Bart & Briskorn, Dirk & Goossens, Dries R. & Spieksma, Frits C.R., 2022. "Parliament seating assignment problems," European Journal of Operational Research, Elsevier, vol. 296(3), pages 914-926.
    3. D. M. King & S. H. Jacobson & E. C. Sewell, 2018. "The geo-graph in practice: creating United States Congressional Districts from census blocks," Computational Optimization and Applications, Springer, vol. 69(1), pages 25-49, January.
    4. Swamy, Rahul & King, Douglas M. & Ludden, Ian G. & Dobbs, Kiera W. & Jacobson, Sheldon H., 2024. "A practical optimization framework for political redistricting: A case study in Arizona," Socio-Economic Planning Sciences, Elsevier, vol. 92(C).
    5. Haase, Knut & Müller, Sven, 2014. "Upper and lower bounds for the sales force deployment problem with explicit contiguity constraints," European Journal of Operational Research, Elsevier, vol. 237(2), pages 677-689.
    6. Eduardo Álvarez-Miranda & Camilo Campos-Valdés & Maurcio Morales Quiroga & Matías Moreno-Faguett & Jordi Pereira, 2020. "A Multi-Criteria Pen for Drawing Fair Districts: When Democratic and Demographic Fairness Matter," Mathematics, MDPI, vol. 8(9), pages 1-26, August.
    7. Han, Jialin & Hu, Yaoguang & Mao, Mingsong & Wan, Shuping, 2020. "A multi-objective districting problem applied to agricultural machinery maintenance service network," European Journal of Operational Research, Elsevier, vol. 287(3), pages 1120-1130.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Rui Fragoso & Conceição Rego & Vladimir Bushenkov, 2016. "Clustering of Territorial Areas: A Multi-Criteria Districting Problem," Journal of Quantitative Economics, Springer;The Indian Econometric Society (TIES), vol. 14(2), pages 179-198, December.
    2. Steiner, Maria Teresinha Arns & Datta, Dilip & Steiner Neto, Pedro José & Scarpin, Cassius Tadeu & Rui Figueira, José, 2015. "Multi-objective optimization in partitioning the healthcare system of Parana State in Brazil," Omega, Elsevier, vol. 52(C), pages 53-64.
    3. Alexander Butsch & Jörg Kalcsics & Gilbert Laporte, 2014. "Districting for Arc Routing," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 809-824, November.
    4. Christian Haas & Lee Hachadoorian & Steven O Kimbrough & Peter Miller & Frederic Murphy, 2020. "Seed-Fill-Shift-Repair: A redistricting heuristic for civic deliberation," PLOS ONE, Public Library of Science, vol. 15(9), pages 1-34, September.
    5. Antonio Diglio & Stefan Nickel & Francisco Saldanha-da-Gama, 2020. "Towards a stochastic programming modeling framework for districting," Annals of Operations Research, Springer, vol. 292(1), pages 249-285, September.
    6. D. M. King & S. H. Jacobson & E. C. Sewell, 2018. "The geo-graph in practice: creating United States Congressional Districts from census blocks," Computational Optimization and Applications, Springer, vol. 69(1), pages 25-49, January.
    7. María Salazar-Aguilar & Roger Ríos-Mercado & Mauricio Cabrera-Ríos, 2011. "New Models for Commercial Territory Design," Networks and Spatial Economics, Springer, vol. 11(3), pages 487-507, September.
    8. Juan A. Díaz & Dolores E. Luna, 2017. "Primal and dual bounds for the vertex p-median problem with balance constraints," Annals of Operations Research, Springer, vol. 258(2), pages 613-638, November.
    9. Sebastián Moreno & Jordi Pereira & Wilfredo Yushimito, 2020. "A hybrid K-means and integer programming method for commercial territory design: a case study in meat distribution," Annals of Operations Research, Springer, vol. 286(1), pages 87-117, March.
    10. Maria da Conceição Rego & Rui Fragoso & Vladimir Bushenkov, 2014. "Clustering of Territorial Areas: A Multi-Criteria Districting Problem," ERSA conference papers ersa14p218, European Regional Science Association.
    11. Eduardo Álvarez-Miranda & Camilo Campos-Valdés & Maurcio Morales Quiroga & Matías Moreno-Faguett & Jordi Pereira, 2020. "A Multi-Criteria Pen for Drawing Fair Districts: When Democratic and Demographic Fairness Matter," Mathematics, MDPI, vol. 8(9), pages 1-26, August.
    12. Baghersad, Milad & Emadikhiav, Mohsen & Huang, C. Derrick & Behara, Ravi S., 2023. "Modularity maximization to design contiguous policy zones for pandemic response," European Journal of Operational Research, Elsevier, vol. 304(1), pages 99-112.
    13. Haugland, Dag & Ho, Sin C. & Laporte, Gilbert, 2007. "Designing delivery districts for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 180(3), pages 997-1010, August.
    14. Anna Franceschetti & Ola Jabali & Gilbert Laporte, 2017. "Continuous approximation models in freight distribution management," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(3), pages 413-433, October.
    15. Swamy, Rahul & King, Douglas M. & Ludden, Ian G. & Dobbs, Kiera W. & Jacobson, Sheldon H., 2024. "A practical optimization framework for political redistricting: A case study in Arizona," Socio-Economic Planning Sciences, Elsevier, vol. 92(C).
    16. Balázs Fleiner & Balázs Nagy & Attila Tasnádi, 2017. "Optimal partisan districting on planar geographies," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(4), pages 879-888, December.
    17. Burcin Bozkaya & Erhan Erkut & Dan Haight & Gilbert Laporte, 2011. "Designing New Electoral Districts for the City of Edmonton," Interfaces, INFORMS, vol. 41(6), pages 534-547, December.
    18. Miguel Ángel Gutiérrez-Andrade & Eric Alfredo Rincón-García & Sergio Gerardo de-los-Cobos-Silva & Pedro Lara-Velázquez & Roman Anselmo Mora-Gutiérrez & Antonin Ponsich, 2019. "Simulated Annealing and Artificial Bee Colony for the Redistricting Process in Mexico," Interfaces, INFORMS, vol. 49(3), pages 189-200, May.
    19. Federica Ricca & Andrea Scozzari & Bruno Simeone, 2013. "Political Districting: from classical models to recent approaches," Annals of Operations Research, Springer, vol. 204(1), pages 271-299, April.
    20. Dilip Datta & Jacek Malczewski & José Rui Figueira, 2012. "Spatial Aggregation and Compactness of Census Areas with a Multiobjective Genetic Algorithm: A Case Study in Canada," Environment and Planning B, , vol. 39(2), pages 376-392, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:60:y:2012:i:5:p:1213-1228. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.