Linear-size formulations for connected planar graph partitioning and political districting
Linear-size formulations for connected planar graph partitioning and political districting
复制标题
连接平面图分区和政治分区的线性大小公式
DOI：
10.1007/s11590-023-02070-0
复制
发表时间：
2024
影响因子：
1.6
通讯作者：
Hicks, Illya V.
中科院分区：
文献类型：
--
作者：
Zhang, Jack;Validi, Hamidreza;Buchanan, Austin;Hicks, Illya V.
受政治选区应用的推动，我们考虑将平面图的顶点划分为连通分量的任务。我们为该任务提出了一个扩展公式，它具有两个理想的属性：（i）它仅使用 O(n) 个变量、约束和非零值，（ii）它是完美的。为了探索其解决现实世界问题的能力，我们将其应用于政治选区问题，其中邻接性和人口平衡被强加为硬约束，并优化紧凑性。计算实验表明，尽管模型规模较小且连通划分完整，但种群平衡约束的有效施加比较困难。尽管如此，我们还是分享我们的发现，希望其他人能找到更好的方法来实施它们。
Motivated by applications in political districting, we consider the task of partitioning thenvertices of a planar graph intokconnected components. We propose an extended formulation for this task that has two desirable properties: (i) it uses justO(n) variables, constraints, and nonzeros, and (ii) it isperfect. To explore its ability to solve real-world problems, we apply it to a political districting problem in which contiguity and population balance are imposed as hard constraints and compactness is optimized. Computational experiments show that, despite the model’s small size and integrality for connected partitioning, the population balance constraints are more troublesome to effectively impose. Nevertheless, we share our findings in hopes that others may find better ways to impose them.
登录
查看更多内容
有界属图的生成树多形体的更小扩展公式
影响因子：
0.8
作者：
Samuel Fiorini;T. Huynh;G. Joret;Kanstantsin Pashkovich
通讯作者：
Kanstantsin Pashkovich
基于多目标生成树的政治选区重新划分优化模型
影响因子：
2.4
作者：
M. Kim
通讯作者：
M. Kim
影响因子：
2.1
作者：
Hamidreza Validi;Austin Buchanan
通讯作者：
Hamidreza Validi;Austin Buchanan
政治选区重划问题的基于连续性的优化模型
DOI：
10.4018/ijagr.2017100101
发表时间：
2017
期刊：
Int. J. Appl. Geospat. Res.
影响因子：
--
作者：
M. Kim;N. Xiao
通讯作者：
N. Xiao
用于小封闭类及其他类中的生成树多胞体的较小扩展公式
DOI：
10.37236/10522
发表时间：
2021
期刊：
Electron. J. Comb.
影响因子：
--
作者：
Manuel Aprile;Samuel Fiorini;T. Huynh;G. Joret;D. Wood
通讯作者：
D. Wood