{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T04:23:03Z","timestamp":1768882983802,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T00:00:00Z","timestamp":1629158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T00:00:00Z","timestamp":1629158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e0 degli Studi di Roma La Sapienza"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Political districting (PD) is a wide studied topic in the literature since the 60s. It typically requires a multi-criteria approach, and mathematical programs are frequently suggested to model the many aspects of this difficult problem. This implies that exact models cannot be solved to optimality when the size of the territory is too large. In spite of this, an exact formulation can also be exploited in a heuristic framework to find at least a sub-optimal solution for large size problem instances. We study the design of electoral districts in Mexico, where the population is characterized by the presence of minority groups (\u201cindigenous community\u201d) who have a special right to be represented in the Parliament. For this, the Mexican electoral law prescribes that a fixed number of districts must be designed to support the representation of the indigenous community. We formulate mixed integer linear programs (MILP) following these two principles, but also including the basic PD criteria of contiguity and population balance. The district map is obtained in two stages: first we produce the fixed number of indigenous districts established by the Law; then we complete the district map by forming the non-indigenous districts. This two-phase approach has two advantages: a dedicated objective function can be formulated in Phase 1 to form indigenous districts at best; in the second phase the instance size is reduced (both in the number of territorial units and in the number of districts) so that the computational effort to solve the problem is reduced as well. We test our procedure on the territory of Chiapas in Mexico and on some fictitious problem instances in which the territory is represented by a grid graph. We also compare our district map with the Institutional one currently adopted in Chiapas.<\/jats:p>","DOI":"10.1007\/s10479-021-04227-5","type":"journal-article","created":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T21:02:57Z","timestamp":1629234177000},"page":"375-402","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Mathematical political districting taking care of minority groups"],"prefix":"10.1007","volume":"305","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8475-4541","authenticated-orcid":false,"given":"Ver\u00f3nica","family":"Arredondo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9405-8830","authenticated-orcid":false,"given":"Miguel","family":"Mart\u00ednez-Panero","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4594-7225","authenticated-orcid":false,"given":"Teresa","family":"Pe\u00f1a","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7925-7911","authenticated-orcid":false,"given":"Federica","family":"Ricca","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,17]]},"reference":[{"key":"4227_CR1","volume-title":"Network flows","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows. Hoboken: Prentice Hall."},{"issue":"2","key":"4227_CR2","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1111\/j.1468-2508.2004.00163.x","volume":"66","author":"SA Banducci","year":"2004","unstructured":"Banducci, S. A., Donovan, T., & Karp, J. A. (2004). Minority representation, empowerment, and participation. The Journal of Politics, 66(2), 534\u2013556.","journal-title":"The Journal of Politics"},{"key":"4227_CR3","doi-asserted-by":"crossref","unstructured":"Cameron, C., Epstain, D., & O\u2019Halloran, S. (1996). Do majority\u2013minority districts maximize substantive black representation congress? American Political Science Review, 90(4), 794\u2013812.","DOI":"10.2307\/2945843"},{"issue":"3","key":"4227_CR4","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1177\/0160017607301605","volume":"30","author":"JC Duque","year":"2007","unstructured":"Duque, J. C., Ramos, R., & Suri\u00f1ach, J. (2007). Supervised regionalization methods: A survey. International Regional Science Review, 30(3), 195\u2013220.","journal-title":"International Regional Science Review"},{"issue":"4","key":"4227_CR5","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1177\/000276426400800407","volume":"8","author":"L Forrest","year":"1964","unstructured":"Forrest, L. (1964). Apportionment by computer. American Behavioral Science, 8(4), 23.","journal-title":"American Behavioral Science"},{"issue":"1","key":"4227_CR6","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0038-0121(96)00016-X","volume":"31","author":"JA George","year":"1997","unstructured":"George, J. A., Lamar, B. W., & Wallace, C. A. (1997). Political district determination using large-scale network optimization. Socio-Economic Planning Sciences, 31(1), 11\u201328.","journal-title":"Socio-Economic Planning Sciences"},{"key":"4227_CR7","doi-asserted-by":"crossref","unstructured":"Grilli di Cortona, P., Manzi, C., Pennisi, A., Ricca F. & Simeone B. (1999). Optimization models for electoral districting. In Evaluation and optimization of electoral systems (pp. 165\u2013190). Philadelphia PA: Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898719819"},{"issue":"6","key":"4227_CR8","doi-asserted-by":"publisher","first-page":"998","DOI":"10.1287\/opre.13.6.998","volume":"13","author":"SW Hess","year":"1965","unstructured":"Hess, S. W., Weaver, J. B., Siegfelatt, H. J., Whelan, J. N., & Zitlau, P. A. (1965). Nonpartisan political redistricting by computer. Operations Research, 13(6), 998\u20131006.","journal-title":"Operations Research"},{"issue":"2","key":"4227_CR9","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0962-6298(93)90031-2","volume":"12","author":"DL Horn","year":"1993","unstructured":"Horn, D. L., Hampton, C. R., & Vandenberg, A. J. (1993). Practical application of district compactness. Political Geography, 12(2), 103\u2013120.","journal-title":"Political Geography"},{"issue":"1","key":"4227_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02578982","volume":"13","author":"J Kalcsics","year":"2005","unstructured":"Kalcsics, J., Nickel, S., & Schroeder, M. (2005). Towards a unified territorial design approach\u2014Applications, algorithms and GIS integration. TOP, 13(1), 1\u201356.","journal-title":"TOP"},{"issue":"3","key":"4227_CR11","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1016\/j.ejor.2020.12.059","volume":"263","author":"FK Miyazawa","year":"2021","unstructured":"Miyazawa, F. K., Moura, P. F. S., Ota, M. J., & Wakabayashi, Y. (2021). Partitioning a graph into balanced connected classes: Formulations, separation and experiments. European Journal of Operational Research, 263(3), 826\u2013836.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"4227_CR12","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0260-9827(87)80003-4","volume":"6","author":"RL Morril","year":"1987","unstructured":"Morril, R. L. (1987). Redistricting, region and representation. Political Geography Quaterly, 6(3), 241\u2013260.","journal-title":"Political Geography Quaterly"},{"key":"4227_CR13","first-page":"89","volume":"15","author":"J Oehlein","year":"2017","unstructured":"Oehlein, J., & Haunert, J.-H. (2017). A cutting-plane method for contiguity-constrained spatial aggregation. Journal of Spatial Information Science, 15, 89\u2013120.","journal-title":"Journal of Spatial Information Science"},{"key":"4227_CR14","doi-asserted-by":"crossref","unstructured":"Ricca, F., & Scozzari, A. (2020). Mathematical programming formulations for practical political districting. In Optimal Districting and Territory Design (pp. 105\u2013128). Cham: Springer.","DOI":"10.1007\/978-3-030-34312-5_6"},{"key":"4227_CR15","unstructured":"Ricca F., Scozzari A. & Serafini P. (2017). A Guided tour of the mathematics of seat allocation and political districting. In U. Endriss (Ed.), Trends in computational social choice (pp. 49\u201368). AI Access."},{"issue":"9\u201310","key":"4227_CR16","doi-asserted-by":"publisher","first-page":"1468","DOI":"10.1016\/j.mcm.2008.05.041","volume":"48","author":"F Ricca","year":"2008","unstructured":"Ricca, F., Scozzari, A., & Simeone, B. (2008). Weighted Voronoi region algorithms for political districting. Mathematical and Computer Modelling, 48(9\u201310), 1468\u20131477.","journal-title":"Mathematical and Computer Modelling"},{"issue":"1","key":"4227_CR17","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10479-012-1267-2","volume":"204","author":"F Ricca","year":"2013","unstructured":"Ricca, F., Scozzari, A., & Simeone, B. (2013). Political districting: From classical models to recent approaches. Annals of Operations Research, 204(1), 271\u2013299.","journal-title":"Annals of Operations Research"},{"issue":"3","key":"4227_CR18","doi-asserted-by":"publisher","first-page":"1409","DOI":"10.1016\/j.ejor.2006.08.065","volume":"189","author":"F Ricca","year":"2008","unstructured":"Ricca, F., & Simeone, B. (2008). Local search algorithms for political districting. European Journal of Operational Research, 189(3), 1409\u20131426.","journal-title":"European Journal of Operational Research"},{"key":"4227_CR19","volume-title":"Optimal districting and territory design","year":"2020","unstructured":"Rios-Mercado, R. Z. (Ed.). (2020). Optimal districting and territory design. Berlin: Springer."},{"key":"4227_CR20","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.omega.2012.08.002","volume":"41","author":"RZ Rios-Mercado","year":"2013","unstructured":"Rios-Mercado, R. Z., & Lopez-Perez, J. F. (2013). Commercial territory design planning with realignment and disjoint assignment requirements. Omega, 41, 525\u2013535.","journal-title":"Omega"},{"issue":"6","key":"4227_CR21","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1068\/b34104","volume":"36","author":"T Shirabe","year":"2009","unstructured":"Shirabe, T. (2009). Districting modeling with exact contiguity constrains. Environment and Planning B: Planning and Design, 36(6), 1053\u20131066.","journal-title":"Environment and Planning B: Planning and Design"},{"key":"4227_CR22","volume-title":"Mathematics and democracy","year":"2006","unstructured":"Simeone, B., & Pukelsheim, F. (Eds.). (2006). Mathematics and democracy. Heidelberg: Springer."},{"issue":"3","key":"4227_CR23","doi-asserted-by":"publisher","first-page":"947","DOI":"10.2307\/1958636","volume":"67","author":"PG Taylor","year":"1973","unstructured":"Taylor, P. G. (1973). A new shape measure for evaluating electoral district patterns. American Political Science Review, 67(3), 947\u2013950.","journal-title":"American Political Science Review"},{"key":"4227_CR24","unstructured":"Validi, H., Buchanan, A., & Lykhovyd, E. (2020). Imposing contiguity constraints in political districting models. Operations Research. Preprint, http:\/\/www.optimization-online.org\/B_HTML\/2020\/01\/7582.html."},{"issue":"1","key":"4227_CR25","doi-asserted-by":"publisher","first-page":"105","DOI":"10.2307\/2145973","volume":"76","author":"W Vickrey","year":"1961","unstructured":"Vickrey, W. (1961). On the prevention of gerrymandering. Political Science Quaterly, 76(1), 105\u2013110.","journal-title":"Political Science Quaterly"},{"issue":"1","key":"4227_CR26","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1111\/j.1435-5597.1995.tb00626.x","volume":"74","author":"JC Williams Jr","year":"1995","unstructured":"Williams, J. C, Jr. (1995). Political redistricting: A review. Papers in Regional Sciences, 74(1), 13\u201340.","journal-title":"Papers in Regional Sciences"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04227-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-021-04227-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04227-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,14]],"date-time":"2021-09-14T14:29:37Z","timestamp":1631629777000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-021-04227-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,17]]},"references-count":26,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["4227"],"URL":"https:\/\/doi.org\/10.1007\/s10479-021-04227-5","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,17]]},"assertion":[{"value":"12 July 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}