# Fairmandering: A column generation heuristic for fairness-optimized political districting

arXiv: https://arxiv.org/abs/2103.11469 · HTML: https://mlsanity.com/paper/2103.11469/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2021.

## Built on by (most cited first, 6 of 6)

- [Redrawing attendance boundaries to promote racial and ethnic diversity in elementary schools](https://mlsanity.com/paper/2303.07603/) (2023)
- [Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans](https://mlsanity.com/paper/2401.17455/) (2024)
- [A Unified Approach to Extract Interpretable Rules from Tree Ensembles via Integer Programming](https://mlsanity.com/paper/2407.00843/) (2024)
- [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024)
- [Merging public elementary schools to reduce racial/ethnic segregation](https://mlsanity.com/paper/2502.10193/) (2025)
- [Fast and Effective Redistricting Optimization via Composite-Move Tabu Search](https://mlsanity.com/paper/2605.06682/) (2026)

## Abstract (arXiv)

The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. Existing computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness. We claim that this is a flawed approach because compactness and fairness are orthogonal qualities, and introduce a scalable two-stage method to explicitly optimize for arbitrary piecewise-linear definitions of fairness. The first stage is a randomized divide-and-conquer column generation heuristic which produces an exponential number of distinct district plans by exploiting the compositional structure of graph partitioning problems. This district ensemble forms the input to a master selection problem to choose the districts to include in the final plan. Our decoupled design allows for unprecedented flexibility in defining fairness-aligned objective functions. The pipeline is arbitrarily parallelizable, is flexible to support additional redistricting constraints, and can be applied to a wide array of other regionalization problems. In the largest ever ensemble study of congressional districts, we use our method to understand the range of possible expected outcomes and the implications of this range on potential definitions of fairness.