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.