CM-Tabu finds theoretical optimum in redistricting with composite moves

Spatial redistricting is a notoriously difficult combinatorial optimization problem, constrained by the requirement that districts remain contiguous. Traditional integer-programming and heuristic methods often get stuck in poor local optima because viable moves are too limited. Hai Jin and Diansheng Guo introduce Composite-Move Tabu Search (CM-Tabu), which overcomes this by systematically expanding the feasible neighborhood space. Instead of only reassigning single boundary units, CM-Tabu identifies composite moves: minimal sets of units that can move together, or pairs of units/sets that can be swapped, all while preserving contiguity. The algorithm leverages articulation points and biconnected components in each district's contiguity graph to generate these candidates in linear time.

Extensive experiments demonstrate CM-Tabu's superiority over traditional Tabu search and other baselines. In the Philadelphia case study, the method consistently attains the theoretical global optimum for population equality—a first for heuristic redistricting approaches. It also enables flexible trade-offs between multiple criteria, such as compactness and demographic balance, without sacrificing solution quality. The computational efficiency gains make it practical for iterative, interactive refinement in real-world redistricting processes.

The implications extend beyond academic interest. CM-Tabu offers a robust, fast tool for redistricting commissions and policymakers, reducing the risk of gerrymandering by enabling fairer, more transparent district maps. As the algorithm can handle large-scale spatial problems, it also opens avenues for applications in logistics, zoning, and other domains requiring contiguous region partitioning.