CAREER: Parsimonious Models for Redistricting

这项教师早期职业发展（Career）资助通过支持科学研究改进重新划分方法来促进国家福利。对分区规划的常见批评包括不平等的地区人口，缺乏连续性或紧凑性，不必要的县分裂（或其他政治细分），或利用人口的人口特征来确保反常的代表性。中立地设计分区规划的挑战导致了许多关于基线和权衡的问题。该项目通过优化方法解决了这些挑战，提供了一种数学上合理、透明的方法。目前的优化公式导致了使用现有方法无法解决的非常大的问题。这项研究将：(i)调查确定重划计划中可能的限制的方法，以及（ii）提供政治中立的方法，使公众了解各种约束如何很好地抑制操纵。教育计划的三个组成部分将有助于激发学生从事运筹学的职业。PI将参与并指导研究生和本科生的研究。将积极寻求来自弱势群体的学生参与该项目，部分方式是与俄克拉何马州路易斯·斯托克斯少数民族参与联盟合作。现有的精确的重新划分模型不能很好地扩展。即使是他们中最优秀的人也开始在县级重新划分选区的例子中挣扎，部分原因是这些模型有大量的变量。为了满足临界人口相等约束，需要更细的粒度级别，这将导致更大的问题。这项研究考虑了新的模型和算法，这些模型和算法有可能处理更大的实例。这在一定程度上是由新研究的乔木模型（Arborescence Models）实现的，该模型利用平面图形的对偶性，同时实现了小尺寸和显著的强度。一些已研究的处理邻近和紧致约束的技术，例如，长度有界切割，是新的，需要很少或不需要额外的变量。这些方法远远超出了基于多商品流或分层图的许多现有方法。对这些方法的研究有可能为具有距离、延迟和紧凑性限制的网络问题提供新的解决方案。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This Faculty Early Career Development (CAREER) grant promotes the national welfare by supporting scientific research into improved methods for redistricting. Common criticisms of districting plans include unequal district populations, a lack of contiguity or compactness, the needless splitting of counties (or other political subdivisions), or the use of demographic characteristics of the population to ensure anomalous representation. The challenge of neutrally designing districting plans leads to many questions about baselines and tradeoffs. This project addresses these challenges through optimization methods that provide a mathematically sound, transparent approach. Current optimization formulations lead to very large problems that cannot be solved using existing methods. This research will: (i) investigate methods for establishing the limits of what is possible in a redistricting plan, and (ii) provide politically neutral methods that can inform the public about how well various constraints can restrain manipulation. The three components of the education plan will serve to excite students about a career in operations research. The PI will engage and mentor graduate and undergraduate students in the research. Students from underrepresented populations will actively be sought to work on the project, in part, through collaboration with the Oklahoma Louis Stokes Alliance for Minority Participation. Existing exact models for redistricting do not scale well. Even the best of them begin to struggle on county-level instances of redistricting due, in part, to the large number of variables defining these models. To satisfy critical population-equality constraints requires a finer level of granularity, which results in an even larger problem. This research considers new models and algorithms that have the potential to handle significantly larger instances. This is enabled, in part, by the newly researched Arborescence Models, which exploit planar graph duality to simultaneously achieve small size and remarkable strength. Some of the researched techniques for handling contiguity and compactness constraints, e.g., length-bounded cuts, are new and require few or no additional variables. These methods go well beyond the many existing approaches based on multi-commodity flows or layered graphs. Investigation of these methods have the potential to enable new solutions to network problems that have distance, latency, and compactness constraints.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.