Imposing Contiguity Constraints in Political Districting Models
Imposing Contiguity Constraints in Political Districting Models
复制标题
DOI：
10.1287/opre.2021.2141
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Hamidreza Validi;Austin Buchanan;Eugene Lykhovyd
中科院分区：
文献类型：
--
作者：
Hamidreza Validi;Austin Buchanan;Eugene Lykhovyd
近60年来，运筹学技术已经协助创建政治选区规划，从整数规划模型开始。这一模式以紧凑为目标，往往产生毗连或接近毗连的地区，但不能保证毗连。在Hamidreza Validi、Austin Buchanan和尤金·莱霍维德的论文“在政治选区划分模型中施加邻接限制”中，作者考虑并分析了四种不同的邻接模型（两种旧模型和两种新模型）。他们的计算机实现可以处理大到印第安纳州（1,511个人口普查区）的重划实例。他们最快的方法是使用分支切割算法，在回调中添加邻接约束。重要的是，许多变量可以通过拉格朗日参数先验地固定为零。所有测试实例和源代码都是公开的。
For nearly 60 years, operations research techniques have assisted in the creation of political districting plans, beginning with an integer programming model. This model, which seeks compactness as its objective, tends to generate districts that are contiguous, or nearly so, but provides no guarantee of contiguity. In the paper “Imposing contiguity constraints in political districting models” by Hamidreza Validi, Austin Buchanan, and Eugene Lykhovyd, the authors consider and analyze four different contiguity models (two old and two new). Their computer implementation can handle redistricting instances as large as Indiana (1,511 census tracts). Their fastest approach uses a branch-and-cut algorithm, where contiguity constraints are added in a callback. Critically, many variables can be fixed to zero a priori by Lagrangian arguments. All test instances and source code are publicly available.