This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/125677
Description
Title
Optimization methods for political redistricting
Author(s)
Dobbs, Kiera W.
Issue Date
2024-06-27
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)
Sreenivas, Ramavarapu S
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
graph partitioning
optimization
local search
integer programming
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
