Fast and Effective Redistricting Optimization via Composite-Move Tabu Search

Researchers present CM-Tabu, a composite-move Tabu search algorithm that solves spatial redistricting optimization problems more effectively by expanding the feasible solution space while maintaining district contiguity constraints. The method uses graph analysis to identify minimal unit movements or swaps that preserve connectivity, achieving superior solution quality and computational efficiency compared to traditional approaches.

This research addresses a fundamental challenge in computational redistricting: balancing optimization quality against hard geometric constraints. Redistricting—the process of redrawing electoral or administrative boundaries—is a high-dimensional combinatorial problem where traditional search algorithms struggle when contiguity requirements limit which moves are feasible. The CM-Tabu approach systematically expands the neighborhood of possible moves by identifying groups of units that can move together without breaking district connectivity, using biconnected component analysis to generate valid transitions in linear time.

The work builds on decades of computational geometry and combinatorial optimization research, but applies novel graph-theoretic insights to a problem with significant real-world impact. Electoral redistricting directly influences political representation, while administrative redistricting affects resource allocation and service delivery. Prior methods either relaxed contiguity constraints—risking invalid solutions—or accepted heavily constrained search spaces that trap algorithms in local optima. CM-Tabu navigates this tradeoff more intelligently.

The practical implications are substantial. The Philadelphia case study shows the algorithm consistently reaches theoretical global optima for population equality while supporting multi-objective optimization for competing goals like racial representation or compactness. This enables decision-support systems that respect mathematical bounds rather than relying on heuristic approximations. For practitioners, this means faster turnaround times for redistricting workflows and greater confidence in solution quality when defending plans legally or politically.

The advancement matters because redistricting occurs on fixed cycles (typically every ten years in the U.S.), and improvements in solution methods directly impact millions of voters and policymakers. Future work likely involves scaling to larger jurisdictions and integrating additional fairness constraints.

• →CM-Tabu expands feasible search neighborhoods by identifying contiguity-preserving composite moves using graph analysis rather than single-unit reassignments alone.
• →The algorithm achieves linear-time candidate generation through articulation point and biconnected component analysis on district connectivity graphs.
• →Philadelphia case study demonstrates consistent achievement of theoretical global optima for population-equality objectives with multi-criteria trade-off support.
• →The approach substantially improves solution robustness across runs and computational efficiency compared to traditional Tabu search and baseline methods.
• →The research enables more reliable decision-support workflows for real-world redistricting practices with mathematically justified solutions.