Imposing Contiguity Constraints in Political Districting Models

• 成果类型: Article
• 署名作者: Validi, Hamidreza; Buchanan, Austin; Lykhovyd, Eugene
• 署名单位: Rice University; Oklahoma State University System; Oklahoma State University - Stillwater; Texas A&M University System; Texas A&M University College Station
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2141
• 发表日期: 2022
• 页码: 867-892
• 关键词: distributions monte-carlo; reduction techniques; tree problem; geo-graph; algorithms; optimization; compactness; heuristics

摘要

Beginning in the 1960s, techniques from operations research began to be used to generate political districting plans. A classical example is the integer programming model of Hess et al. [Hess SW, Weaver JB, Siegfeldt HJ, Whelan JN, Zitlau PA (1965) Oper. Res. 13(6):998-1006.]. Because of the model's compactness-seeking objective, it tends to generate contiguous or nearly contiguous districts, although none of the model's constraints explicitly impose contiguity. Consequently, Hess et al. had to manually adjust their solutions to make them contiguous. Since then, there have been several attempts to adjust the Hess model and other models so that contiguity is explicitly ensured. In this paper, we review two existing models for imposing contiguity, propose two new ones, and analytically compare them in terms of their strength and size. We conduct an extensive set of numerical experiments to evaluate their performance. Although many believe that contiguity constraints are particularly difficult to deal with, we find that the districting problem considered by Hess et al. does not become harder when contiguity is imposed. In fact, a branch-and-cut implementation of a cut-based model generates, for the first time, optimally compact districting plans for 21 different U.S. states at the census tract level. To encourage future research in this area, and for purposes of transparency, we make our test instances and source code publicly available.