Imposing Contiguity Constraints in Political Districting Models

Hamidreza Validi; Austin Buchanan; Eugene Lykhovyd

doi:10.1287/opre.2021.2141

Imposing Contiguity Constraints in Political Districting Models

Hamidreza Validi¹; Austin Buchanan²; Eugene Lykhovyd³

¹ Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005; · ² School of Industrial Engineering & Management, Oklahoma State University, Stillwater, Oklahoma 74078; · ³ Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas 77843

Operations Research 2022

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.

DOI: 10.1287/opre.2021.2141
Volume: 70 (2)
Pages: 867-892
Language: en
Export: BibTeX
Sources: crossref