When constructing political districting plans, prominent criteria include population balance, contiguity, and compactness. The compactness of a districting plan, which is often judged by the ``eyeball test,'' has been quantified in many ways, e.g., Length-Width, Polsby-Popper, and Moment-of-Inertia. This paper considers the number of cut edges, which has recently gained traction in the redistricting literature as a measure of compactness because it is simple and reasonably agrees with the eyeball test. We study the stylized problem of minimizing the number of cut edges, subject to constraints on population balance and contiguity. With the integer programming techniques proposed in this paper, all county-level instances in the USA (and some tract-level instances) can be solved to optimality. Our techniques easily extend to minimize \emph{weighted} cut edges (e.g., to minimize district perimeter length) or to impose compactness \emph{constraints}. All data, code, and results are on GitHub.
Citation
To appear at Mathematical Programming Computation.