Linear-size formulations for connected planar graph partitioning and political districting
Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation for this task that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2024
|
| Online Access: | https://hdl.handle.net/1721.1/153305 |
| _version_ | 1826198406331105280 |
|---|---|
| author | Zhang, Jack Validi, Hamidreza Buchanan, Austin Hicks, Illya V. |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Zhang, Jack Validi, Hamidreza Buchanan, Austin Hicks, Illya V. |
| author_sort | Zhang, Jack |
| collection | MIT |
| description | Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation for this task that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, we apply it to a political districting problem in which contiguity and population balance are imposed as hard constraints and compactness is optimized. Computational experiments show that, despite the model’s small size and integrality for connected partitioning, the population balance constraints are more troublesome to effectively impose. Nevertheless, we share our findings in hopes that others may find better ways to impose them. |
| first_indexed | 2024-09-23T11:04:23Z |
| format | Article |
| id | mit-1721.1/153305 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:19:48Z |
| publishDate | 2024 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1533052024-12-21T05:51:18Z Linear-size formulations for connected planar graph partitioning and political districting Zhang, Jack Validi, Hamidreza Buchanan, Austin Hicks, Illya V. Massachusetts Institute of Technology. Operations Research Center Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation for this task that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, we apply it to a political districting problem in which contiguity and population balance are imposed as hard constraints and compactness is optimized. Computational experiments show that, despite the model’s small size and integrality for connected partitioning, the population balance constraints are more troublesome to effectively impose. Nevertheless, we share our findings in hopes that others may find better ways to impose them. 2024-01-11T14:55:08Z 2024-01-11T14:55:08Z 2023-10-05 2024-01-11T04:30:49Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/153305 Zhang, Jack, Validi, Hamidreza, Buchanan, Austin and Hicks, Illya V. 2023. "Linear-size formulations for connected planar graph partitioning and political districting." en https://doi.org/10.1007/s11590-023-02070-0 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Zhang, Jack Validi, Hamidreza Buchanan, Austin Hicks, Illya V. Linear-size formulations for connected planar graph partitioning and political districting |
| title | Linear-size formulations for connected planar graph partitioning and political districting |
| title_full | Linear-size formulations for connected planar graph partitioning and political districting |
| title_fullStr | Linear-size formulations for connected planar graph partitioning and political districting |
| title_full_unstemmed | Linear-size formulations for connected planar graph partitioning and political districting |
| title_short | Linear-size formulations for connected planar graph partitioning and political districting |
| title_sort | linear size formulations for connected planar graph partitioning and political districting |
| url | https://hdl.handle.net/1721.1/153305 |
| work_keys_str_mv | AT zhangjack linearsizeformulationsforconnectedplanargraphpartitioningandpoliticaldistricting AT validihamidreza linearsizeformulationsforconnectedplanargraphpartitioningandpoliticaldistricting AT buchananaustin linearsizeformulationsforconnectedplanargraphpartitioningandpoliticaldistricting AT hicksillyav linearsizeformulationsforconnectedplanargraphpartitioningandpoliticaldistricting |