Collaborative Research: High-Performance Computational Standards For Redistricting

协作研究：重新划分的高性能计算标准

• 批准号: 1728902
• 负责人: Bruce Cain
• 金额: $ 24.22万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-15 至 2022-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1728902&HistoricalAwards=false
• 关键词: Collaborative; Research; Performance; Computational; Standards

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.

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