Imposing Contiguity Constraints in Political Districting Models

Hamidreza Validi (), Austin Buchanan () and Eugene Lykhovyd ()
Additional contact information
Hamidreza Validi: Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005
Austin Buchanan: School of Industrial Engineering & Management, Oklahoma State University, Stillwater, Oklahoma 74078
Eugene Lykhovyd: Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas 77843

Operations Research, 2022, vol. 70, issue 2, 867-892

Abstract: 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.

Keywords: Policy Modeling and Public Sector OR; political redistricting; contiguity; connectivity; integer programming; branch-and-cut; Lagrangian; moment-of-inertia (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2141 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:2:p:867-892

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().