Optimization approaches for political districting and graph partitioning

Swamy, Rahul

Permalink

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

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

Copyright and License Information

Copyright 2023 Rahul Swamy

Owning Collections