CAREER: Parsimonious Models for Redistricting

这项教职早期职业发展(职业)补助金通过支持改进重新划分选区的方法的科学研究来促进国家福利。对分区计划的常见批评包括：选区人口不平等、缺乏邻接性或紧凑性、县(或其他政治分区)不必要的分裂，或利用人口的人口特征来确保不正常的代表性。中立地设计选区划分计划的挑战导致了许多关于基线和权衡的问题。这个项目通过优化方法来解决这些挑战，这些方法提供了一种数学上合理、透明的方法。目前的优化公式导致了使用现有方法无法解决的非常大的问题。这项研究将：(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.