Optimization methods for political redistricting

Political redistricting in the U.S. can involve substantial partisan tension and multiple competing interests. Because a district plan divides a collection of geographic units into nonempty, disjoint subsets, redistricting can be viewed as a graph partitioning problem. Therefore, to promote fairness, transparency, and compromise, this dissertation develops optimization methods for political redistricting based on concepts in graph partitioning. First, we consider the problem of optimizing district plans with respect to fairness objectives, subject to legal constraints. A redistricting optimization problem is typically intractable for realistically-sized instances; therefore, we develop a new local search heuristic based on concepts from district plan sampling. This heuristic can produce plans with excellent fairness objective values because it uses a larger search neighborhood than previous methods. We first apply this new local search heuristic to analyze Missouri redistricting. Then we conduct a broader, empirical study comparing variants of this new local search heuristic to previous local search methods. Next, we present an optimization framework to promote compromise between two stakeholders in the redistricting process. We formulate a mixed-integer linear program to find a midpoint between two proposed plans/partitions with respect to a distance metric on graph partitions. Then we extend this formulation to find a sequence of fractional points between two proposed plans/partitions. Generating midpoints or other fractional points can help the redistricting stakeholders visualize how their plans agree, disagree, and how a possible compromise could be realized. Lastly, we extend the notion of finding a sequence of fractional points between two district plans to the problem of finding a shortest path between two connected partitions. We design an A* search algorithm to find such a shortest path. Then because this exact A* algorithm can be intractable for a number of instances, we also propose a heuristic to more tractably obtain near-optimal solutions.

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

2024

Author dc:creator

• Dobbs, Kiera W.

Contributors dc:contributor

• King, Douglas M
• Jacobson, Sheldon H
• Sreenivas, Ramavarapu S
• Garg, Jugal

• Political Redistricting
• Graph Partitioning
• Optimization
• Local Search
• Integer Programming

Statement dc:rights

• Copyright 2024 Kiera Dobbs

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

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