Optimization Online


Imposing contiguity constraints in political districting models

Hamidreza Validi (hamidreza.validi***at***rice.edu)
Austin Buchanan (buchanan***at***okstate.edu)
Eugene Lykhovyd (lykhovyd***at***tamu.edu)

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. (Operations Research 13(6):998--1006, 1965). Due to 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. While 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 US 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: political redistricting; contiguity; connectivity; integer programming; branch-and-cut; Lagrangian; moment-of-inertia;

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming

Category 3: Combinatorial Optimization

Citation: To appear at Operations Research

Download: [PDF]

Entry Submitted: 01/26/2020
Entry Accepted: 01/27/2020
Entry Last Modified: 06/14/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society