For decades, researchers have complained that contiguity constraints make problems like districting much harder than other combinatorial optimization problems. This has prompted the use of integer programming models with inexact contiguity constraints that may be fast in practice but are invalid in the sense that they cut off or “overlook” some contiguous solutions. Examples include the tree-based constraints of Zoltners and Sinha (Management Science, 1983), the distance-based constraints of Mehrotra et al. (Management Science, 1998), and the DAG-based constraints of Shahmizad and Buchanan (Operations Research, 2025). In this paper, we compare these models for imposing contiguity, both analytically and computationally. We identify their sizes, the number of solutions that they admit, the precise conditions under which they are integral, and the computational complexity of optimizing over them. For example, we can optimize a linear objective over the tree-based constraints in polynomial time, but the same problem is NP-hard for distance-based constraints. To reveal the strengths and weaknesses of these models in practice, we use them to draw political districts at different levels of granularity—counties (n~100 vertices), voting precincts (n~2,500), and census blocks (n~175,000)—also comparing with exact methods. The experiments reveal some surprising phenomena, e.g., on the largest graphs, the largest model (DAG) not only produces the best solutions, but also solves quickest. Finally, we report how many enacted congressional and legislative districts across the USA satisfy the various inexact contiguity constraints. The result is a guide to the effectiveness and computational limits of each approach and a codebase for future researchers.
Citation
Submitted to a journal. Code available at https://github.com/Ishaanjolly/A-guide-to-inexact-contiguity-constraints