Fast and Effective Redistricting Optimization via Composite-Move Tabu Search

Authors: Hai Jin, Diansheng Guo

arXiv · PDF

Summary

The authors tackle the combinatorial optimization problem of redrawing electoral district boundaries (redistricting) under constraints like contiguity (every district must be geographically connected). Traditional Tabu search struggles because the contiguity constraint shrinks the feasible neighborhood—many single-unit moves would disconnect a district. They introduce composite-move Tabu search (CM-Tabu), which identifies minimal sets of units that can move together or swap to preserve contiguity, expanding the search neighborhood. The method uses articulation points and biconnected components from graph theory to generate these moves in linear time. Experiments show CM-Tabu substantially improves solution quality, robustness, and speed versus traditional Tabu search, even hitting the theoretical global optimum in the Philadelphia case.

Main takeaways:

• Contiguity constraints in redistricting severely limit the neighborhood for local search, trapping algorithms in poor local optima.
• CM-Tabu expands the feasible neighborhood by allowing composite moves (sets of units moving together or swapping) that preserve contiguity.
• Uses articulation points and biconnected components to generate candidate moves efficiently (linear time per district).
• Consistently improves solution quality and run-to-run robustness over traditional Tabu search and baselines.
• In the Philadelphia case, reliably finds the theoretical global optimum for population equality and supports multi-criteria trade-offs.

Relevance

No connection to my work on language model personas, behavior installation, or conditional behavior. This is a combinatorial optimization paper for geographic redistricting. Included for completeness but not relevant to my research themes.

Abstract

arXiv:2605.06682v1 Announce Type: new Abstract: Spatial redistricting is a practical combinatorial optimization problem that demands high-quality solutions, rapid turnaround, and flexibility to accommodate multi-criteria objectives and interactive refinement. A central challenge is the contiguity constraint: enforcing contiguity in integer-programming or heuristic search can severely shrink the feasible neighborhood, weaken exploration, and trap the search in poor local optima. We introduce a composite-move Tabu search (CM-Tabu) that systematically expands the feasible neighborhood space in Tabu search while preserving contiguity. When a boundary unit cannot be reassigned individually without disconnecting its district, our method identifies a minimal set of units that can move together, or a pair of units (or sets of units) that can be switched, as a contiguity-preserving composite move. Candidate single-unit and composite moves are generated in linear time by analyzing each district's contiguity graph using articulation points and biconnected components. Extensive experiments demonstrate that the proposed approach substantially improves solution quality, run-to-run robustness, and computational efficiency relative to traditional Tabu search and other baselines. For example, in the Philadelphia case, the approach can consistently attain the theoretical global optimum in population-equality and support multi-criteria trade-offs. CM-Tabu delivers optimization performance suitable for real-world practices and decision-support workflows.