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.