CAREER: Parsimonious Models for Redistricting

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

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.