Collaborative Research: High-Performance Computational Standards For Redistricting

这个项目开发的计算工具客观地评估重划选区计划，并自动创建重划选区计划，以满足用户选择的特定标准。该工具将提供一种机制，供决策者在谈判重新划分选区计划时使用，消除当只有少数政治利益集团才能获得数据和提出计划的能力时产生的固有偏见。该项目将涉及多个要素，即：将重新划分选区问题描述为离散的优化问题，引入定量测量以根据广泛的标准对地图进行评分，为重新划分选区问题创建定制的新优化算法，以确定根据给定标准得分较高的地图，并创建允许各州、个人和政党谈判重新划分选区计划的计算工具。除了计算工具的开发外，该项目还将详细研究如何使用计算模型来提供新的实质性见解，并帮助在美国重新划分选区的过程中创建公平标准。尽管经过几十年的努力，这样的标准一直难以捉摸。这项工作的更广泛影响旨在通过向更广泛和更多样化的利益攸关方群体开放参与来改变即将到来的几轮选区重新划分。同样，该工具将为制定重划选区计划提供比以往任何时候都更大的灵活性和增强的能力。在研究领域，算法开发也将适用于使用大规模并行计算架构的大规模优化问题。该项目还有助于研究生教育，提供关于计算方法应用于一系列社会科学问题的指导。技术摘要这项工作的贡献横跨多个学科，包括政治学、法学、计算机科学、数学、运筹学和超级计算。在计算机科学和超级计算领域，这项研究将调整并使并行遗传算法库能够扩展到数十万个处理器。该算法改进了大型组合优化问题的运筹学启发式算法。该实现是一种混合的元启发式算法，将进化算法的搜索能力与多样化和集约化的精细化相结合，以增强更高效的搜索过程。这种数学方法产生了对政治现象的新的量化测量。在政治学和法学领域，该项目将创造一种新的综合和分析大量数据的能力，这些数据将产生关于重新划分选区的公平标准以及重新划分选区对民主进程的效果和影响的新的实质性见解。

General AbstractThis project develops computational tools that objectively evaluate redistricting plans, and automate the creation of redistricting plans to satisfy particular criteria selected by users. The tool will provide a mechanism for decision-makers to use when negotiating redistricting plans, eliminating the inherent bias that arises when the data and the ability to propose plans are available to only a few political interests. The project will entail multiple elements, namely: formulate the redistricting problem as a discrete optimization problem, introduce quantitative measurements to score maps on a wide set of criteria, create novel optimization algorithms customized for the redistricting problem to identify maps that score well on given criteria, and create a computational tool that allows states, individuals, and political parties to negotiate redistricting plans. In addition to the development of the computational tool, this project will engage in a detailed study of how to use computational models to shed new substantive insight and aid in the creation of fairness standards in the American redistricting process. Such standards have been elusive despite decades of effort. The broader impact of the work seeks to transform the upcoming future redistricting rounds by opening it up to participation to a broader and more diverse group of stakeholders. Likewise the tool will provide greater flexibility and enhanced capabilities for developing redistricting plans than ever before. In the research realm, the algorithm development will also be applicable to large-scale optimization problems that utilize massively parallel computing architecture. The project also contributes to graduate education, providing instruction about the application of computational approaches to an array of social scientific questions.Technical AbstractThe contributions of this work span a variety of disciplines including political science, law, computer science, math, operations research, and supercomputing. In the computer science and supercomputing realm, the research will tune and enable a parallel genetic algorithm library to scale to hundreds of thousands of processors. The algorithm advances operations research heuristics for large combinatorial optimization problems. The implementation is a hybrid metaheuristic that combines the search capabilities of evolutionary algorithms with refinements for diversification and intensification to empower a more efficient and effective search process. The mathematical approach yields new quantitative measures of political phenomenon. In political science and law, the project will create a new ability to synthesize and analyze massive amounts of data that will yield new substantive insights about fairness standards for redistricting as well as the effect and impact of redistricting on the democratic process.