10/12/2017 | 4:15pm | E51-335

Reception to follow.

Sheldon Jacobson

GEBI Founder Professor in Engineering
University of Illinois

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.) 

Bio: Sheldon H. Jacobson is a Founder Professor of Engineering, and Director of the Simulation and Optimization Laboratory and the Bed Time Research Institute at the University of Illinois. He has a broad set of basic and applied research interests, including problems related to optimal decision-making, national security, public health, and sports. His research has been disseminated in numerous journals, including Operations Research, Mathematical Programming, and SIAM Journal on Control and Optimization, among others. His research has been supported by the National Science Foundation and the Air Force Office of Scientific Research. He is a Fellow of INFORMS and IISE.