Title: Efficient Methods for Enforcing Contiguity in Geographic Districting Problems

Abstract: Every ten years, United States Congressional Districts must be redesigned in response to a national census. While the size of practical political districting problems is typically too large for exact optimization approaches, heuristics such as local search can help stakeholders quickly identify good (but suboptimal) plans that suit their objectives. However, enforcing a district contiguity constraint during local search can require significant computation; tools that can reduce contiguity-based computations in large practical districting problems are needed. This talk introduces the geo-graph framework for modeling geographic districting as a graph partitioning problem, discusses two geo-graph contiguity algorithms, and applies these algorithms to the creation of United States Congressional Districts from census blocks in several states. The experimental results demonstrate that the geo-graph contiguity assessment algorithms reduce the average number of edges visited during contiguity assessments by at least three orders of magnitude in every problem instance when compared with simple graph search, suggesting that the geo-graph model and its associated contiguity algorithms provide a powerful constraint assessment tool to political districting stakeholders. Joint work with Douglas M. King and Edward C. Sewell