Political Districting
MILP partition · compactness · gerrymandering critique
Partitioning a state's census units into legislative districts seems like a purely geometric problem: equal population, contiguous, compact. It is not. Every line drawn elects a representative, advantages one party over another, concentrates or disperses a racial minority, and carries downstream consequences for a decade. Hess et al. (1965) proposed the first computational formulation; Altman (1997) proved the general problem NP-hard; a generation of MILP and Markov-chain ensemble methods has followed. What no mathematical framework resolves is the ethics of which objective to minimise.
Problem context
One person one vote — and the line that makes it true
After each decennial census, US states redraw the boundaries of their congressional and state-legislative districts to equalise population per district (the one person, one vote doctrine from Reynolds v. Sims, 1964). The operational question: given n census units (tracts, precincts, blocks) with populations pi, partition them into K districts so that each district has roughly P/K people, every district is geographically contiguous, and each district is “compact” by some measure.
Hess et al. (1965) published the first computational formulation in Operations Research: districts as cells in a weighted “centre of gravity” partition, solved by iteration similar to what we would now call constrained k-means. Garfinkel & Nemhauser (1970) reformulated as set partitioning. Mehrotra, Johnson & Nemhauser (1998) brought modern MILP with column generation. Altman (1997) proved that automated redistricting — satisfying compactness, contiguity, and equal-population simultaneously — is NP-hard, closing the door on polynomial-time “optimal” districting.
More recent work has turned from finding one good map to sampling ensembles: Chen & Rodden (2013), DeFord, Duchin & Solomon (2021), and others use Markov-chain Monte Carlo to generate thousands of plausible compact maps, then compare a proposed map against the ensemble distribution. This has become the de facto technique for courts evaluating partisan gerrymandering claims.
Multi-stakeholder framing
Mathematical formulation
The set-partitioning MILP, compactness objectives, and their alternatives
| Symbol | Definition | Domain |
|---|---|---|
| N | Set of census units (tracts, precincts) | |N| = n |
| K | Number of districts to form | ℕ⁺ |
| pi | Population of unit i | ℕ⁺ |
| P | Total population = Σi pi | ℕ⁺ |
| ε | Allowed population deviation (e.g., ±1% or ±5%) | [0, 1] |
| xik | Binary: 1 if unit i is in district k | {0, 1} |
| dij | Centroid distance between units i and j | ℝ⁺ |
| N(i) | Adjacency set of unit i (shared boundary) | N(i) ⊆ N |
s.t. Σk xik = 1 ∀ i // each unit in exactly one district
(1 - ε) P/K ≤ Σi pi xik ≤ (1 + ε) P/K ∀ k // equal population ±ε
district k is contiguous in graph (N, edges) // flow / cut-based contiguity constraints
xik ∈ {0, 1}
Alternative compactness objectives Polsby-Popper: PPk = 4π · Areak / Perimeterk2 (closer to 1 = more compact)
Reock: Areak / Area(smallest enclosing circle)
Cut-edge: # edges in adjacency graph crossing district boundaries (minimise)
Contiguity is a surprisingly difficult constraint to express as linear inequalities. A common approach uses flow variables on a spanning tree of each district (a single unit is designated “root”; every other unit in the district must send a unit of flow toward root through in-district edges). Alternative formulations use cut-set inequalities and lazy constraint generation. Shirabe (2009) reviews these approaches.
Alternative objectives matter. Minimising moment of inertia often produces different maps than minimising cut-edge count or maximising Polsby-Popper score on the same instance. A state can be simultaneously “compact” by one measure and “non-compact” by another. There is no neutral objective choice.
Partisan-fairness metrics live outside the geometric objectives but are increasingly in view. Stephanopoulos & McGhee (2015)'s efficiency gap measures wasted votes asymmetrically between parties; the mean-median gap compares mean district vote share to median district vote share. Either can be embedded as a soft constraint or as a fairness objective alongside compactness.
Interactive solver
Partition a grid state into K districts; compare compactness measures
Grid Districting Solver
About the solver. A grid state is a dramatic simplification: real census tracts have irregular shapes, embedded water / unbuildable areas, and jurisdictional subdivisions (counties, wards) that districts must generally respect. The solver uses a seeded BFS-growth heuristic that maintains contiguity by construction, then improves the chosen objective with swap moves between adjacent districts. Production tools (e.g. GerryChain, Auto-Redistrict) implement ReCom MCMC for ensemble sampling, which is dramatically more sophisticated — see Extensions.
Solution interpretation
What the map tells — and what it hides
Different compactness objectives produce visibly different maps. Moment of inertia favours round, concentric districts. Cut-edge favours squat blocks that minimise boundary. Polsby-Popper maximises interior-to-perimeter ratio and tends to produce rectangular shapes.
Urban-cluster population distributions expose an efficiency-equity tension. When population concentrates in one region, the population-equality constraint forces districts to reach far into lower-density areas, making them less geometrically compact. This is a real feature of every state with major metro areas.
Compactness does not prevent gerrymandering. It is perfectly possible to draw a partisan-biased map where every district is compact by any metric. “Pack and crack” can be done inside compact shapes by choosing which adjacent urban and rural units to combine. The tools for detecting gerrymandering (partisan-fairness metrics, ensemble comparison) are separate from compactness.
What voters care about: Whose representative are they? Are they grouped with their natural political community? What courts care about: Did the drawing body follow stated neutral criteria and VRA compliance? What reform groups care about: Does the final map differ meaningfully from a neutral ensemble sample?
Limitations & Critique
Why compactness is not neutrality
Compactness does not prevent gerrymandering
A partisan map can satisfy any individual compactness metric while still systematically advantaging one party via targeted pack-and-crack at the unit level. Compactness is necessary but not sufficient for fairness. Ensemble methods, not compactness bounds, are the modern tool.
There is no neutral objective
Moment of inertia, Polsby-Popper, Reock, cut-edge, and convex-hull measures all produce different optima on the same instance. Any objective embodies a theory of what “good” districting looks like; the choice is political, not technical.
Partisan fairness vs. racial fairness can conflict
Voting Rights Act §2 requires majority-minority districts where protected-class voters can elect their preferred candidate. Drawing such districts can reduce overall partisan symmetry and vice versa. The Supreme Court has been inconsistent on how much racial consideration is permitted; this is contested ground, not settled law.
NP-hardness means no “optimal” solution is findable
Altman (1997) proved that jointly optimising compactness, contiguity, and population equality is NP-hard. Any tool claiming to find “the optimal” map is either running a heuristic or restricting the problem. Ensemble methods explicitly acknowledge this: sample many, compare to the proposed map statistically.
Census data carries its own biases
The input populations pi are themselves model outputs. The 2020 US Census had documented differential undercounts for Hispanic, Black, and Native American populations. Districts drawn on undercounted data systematically under-represent those communities, independent of whatever optimisation runs on top.
Court review has been inconsistent
Rucho v. Common Cause (2019) held that federal courts cannot adjudicate partisan-gerrymandering claims. State courts in some states have stepped in (PA, NC) using state-constitutional grounds. The legal framework is unstable; any OR-driven proposal must be framed for whichever forum will actually review it.
Extensions & variants
Where the field is now
MCMC ensemble sampling (ReCom)
DeFord, Duchin & Solomon (2021). Generate thousands of compact plans via spanning-tree-based recombination; compare proposed map statistically to the ensemble.
Majority-minority VRA constraints
Reserve districts where a protected class has population share sufficient to elect their preferred candidate. Thornburg v. Gingles three-part test.
Partisan-fairness metrics
Efficiency gap (Stephanopoulos-McGhee 2015), mean-median gap, partisan symmetry, declination. Each proxies a different normative notion of fairness.
Column-generation MILP
Mehrotra, Johnson & Nemhauser (1998). Enumerate feasible-district columns; master problem selects a feasible partition.
Cut-edge minimisation
Herschlag et al. (2020). Minimise number of edges in adjacency graph crossing district boundaries — an integer objective with interpretable compactness meaning.
GerryChain / auto-redistrict
Open-source tooling (MGGG, Auto-Redistrict) for academic and advocacy ensemble analysis; used in expert testimony.
Community-of-interest constraints
Keep recognised communities (ethnic neighbourhoods, Tribal lands, school districts) intact. Increasingly encoded in state redistricting statutes.
Multi-objective approaches
ε-constraint or weighted-sum across compactness, VRA compliance, county-preservation, partisan-symmetry. DeFord et al. (2020); Swamy-Jacobson-Magazine (2022) review.
Key references
Cited above · DOIs where available
Related applications
Other public-services partitioning and critical-lens problems