Optimization approaches for political districting and graph partitioning

Graph partitioning (GP) is the problem of dividing a graph into smaller subgraphs with desired properties. GP is valuable in a variety of domains such as social, transportation and power networks. A notable application of GP is in political districting in the U.S., where congressional and state legislative districts are redrawn every ten years. Existing studies that model political districting as a GP have explored exact, heuristic, and game theoretical techniques. However, these studies have three key drawbacks: (i) they disregard political fairness considerations that are increasingly valued in legal requirements, (ii) the methods are computationally intractable to large input sizes, and (iii) they do not capture the numerous and complex needs of a practical districting process. This dissertation provides optimization formulations for fair political districting and heuristic frameworks that scale for large input sizes. This dissertation consists of four parts. The first part addresses the issue of fairness in political districting by providing Mixed Integer Programming (MIP) formulations that optimize fundamental fairness such as efficiency gap, partisan asymmetry, and competitiveness. Three bi-criteria problems are solved using a proposed multilevel algorithm, which generates approximate-Pareto optimal solutions, illustrating the trade-off between compactness and each of the partisan fairness metrics. The second part provides a case study on districting in Arizona, capturing all the legal criteria in Arizona’s Constitution. This multi-stage local-search powered framework demonstrates how optimization algorithms can generate viable solutions to practical districting. The third part provides heuristic strategies for two sequential game protocols, namely the bisection and I-cut-you-freeze protocols, where the drawing decision in each round is modeled as an MIP. A computational investigation for real-world congressional districting in 18 states indicates that neither protocol is fairer than the other, although both provide an improvement to the status quo. Beyond political districting, the fourth part introduces a variant of GP with high connectivity requirements, called the Highly Connected Graph Partitioning (HCGP) problem. This problem is valuable in applications that require cohesion and fault-tolerance within their parts, such as community detection in social networks and resiliency-focused partitioning of power networks. This work provides an Integer Programming model for HCGP and solution methods to solve instances derived from a diverse set of real-world graphs. Overall, the models and methods presented in this dissertation serve as effective tools to capture fairness in political districting and resiliency in GP.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Swamy, Rahul

Contributors dc:contributor

• King, Douglas M.
• Jacobson, Sheldon H.
• Beck, Carolyn L.
• Garg, Jugal

• Political Redistricting
• Optimization
• Gerrymandering
• Graph Theory
• Graph Partitioning
• Fairness
• Fault-tolerant Partitioning
• Public Policy

Statement dc:rights

• Copyright 2023 Rahul Swamy

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121994

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121994