University of Illinois Urbana-Champaign

Optimization approaches for political districting and graph partitioning

Swamy, Rahul

Content Files
SWAMY-DISSERTATION-2023.pdf

Permalink

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

Description

Title
Optimization approaches for political districting and graph partitioning
Author(s)
Swamy, Rahul
Issue Date
2023-11-29
Director of Research (if dissertation) or Advisor (if thesis)
  • King, Douglas M.
  • Jacobson, Sheldon H.
Doctoral Committee Chair(s)
King, Douglas M.
Committee Member(s)
  • Beck, Carolyn L.
  • Garg, Jugal
Department of Study
Industrial&Enterprise Sys Eng
Discipline
Industrial Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Political redistricting, optimization, gerrymandering, graph theory, graph partitioning, fairness, fault-tolerant partitioning, public policy
Abstract
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.
Graduation Semester
2023-12
Type of Resource
Thesis
Handle URL
https://hdl.handle.net/2142/121994
Copyright and License Information
Copyright 2023 Rahul Swamy

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois