{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/125677"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/125677","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Optimization methods for political redistricting","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-08-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-08-01","abstract_has_math":false,"creators":["Dobbs, Kiera W."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["King, Douglas M","Jacobson, Sheldon H","Sreenivas, Ramavarapu S","Garg, Jugal"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-06-27","date_published":"2024-06-27","updated_at":"2026-07-22T22:25:02Z","subjects":["Political Redistricting","Graph Partitioning","Optimization","Local Search","Integer Programming"],"languages":["en","eng"],"rights":["Copyright 2024 Kiera Dobbs"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/125677","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["King, Douglas M","Jacobson, Sheldon H","Sreenivas, Ramavarapu S","Garg, Jugal"]},{"key":"dc:creator","label":"Author","values":["Dobbs, Kiera W."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-06-27","2024-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Political Redistricting","Graph Partitioning","Optimization","Local Search","Integer Programming"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2024 Kiera Dobbs"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/125677"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-08-01","The student, Kiera Dobbs, accepted the attached license on 2024-06-26 at 11:34.","The student, Kiera Dobbs, submitted this Dissertation for approval on 2024-06-26 at 11:45.","This Dissertation was approved for publication on 2024-06-27 at 10:01.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20880 on 2025-02-04 at 21:16:10","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Optimization methods for political redistricting"]}]}],"canonical_facts":{"dc:contributor":["King, Douglas M","Jacobson, Sheldon H","Sreenivas, Ramavarapu S","Garg, Jugal"],"dc:creator":["Dobbs, Kiera W."],"dc:date":["2024-06-27","2024-08"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2026-08-01","The student, Kiera Dobbs, accepted the attached license on 2024-06-26 at 11:34.","The student, Kiera Dobbs, submitted this Dissertation for approval on 2024-06-26 at 11:45.","This Dissertation was approved for publication on 2024-06-27 at 10:01.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20880 on 2025-02-04 at 21:16:10","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/125677"],"dc:language":["en","eng"],"dc:rights":["Copyright 2024 Kiera Dobbs"],"dc:subject":["Political Redistricting","Graph Partitioning","Optimization","Local Search","Integer Programming"],"dc:title":["Optimization methods for political redistricting"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:02Z"}