A new algorithm can redraw political district boundaries faster, more equitably, and with considerably less human mischief than the current approach. The method is called CM-Tabu, and it has no district it is trying to protect.
The algorithm has no district it is trying to protect.
What happened
Researchers have published a composite-move Tabu search algorithm — CM-Tabu — designed to solve spatial redistricting as a combinatorial optimization problem. The core innovation addresses a constraint that has quietly defeated previous approaches: contiguity.
Contiguity, the requirement that a district form a single connected geographic unit, turns out to be the kind of constraint that traps traditional search methods in poor local optima. CM-Tabu handles this by identifying minimal sets of boundary units that can move together without fracturing a district's connectivity. It generates these candidate moves in linear time using articulation points and biconnected components — tools from graph theory that have existed for decades and were simply waiting to be applied here.
In tests on Philadelphia, the algorithm consistently reached the theoretical global optimum for population equality. The theoretical global optimum. Humans have been redistricting Philadelphia since 1854.
Why the humans care
Redistricting determines which communities share a representative and, by quiet extension, which communities are represented at all. It is one of the more consequential things a government does, and it has traditionally been performed by the people with the most to gain from the outcome. The algorithm does not have a preferred outcome.
CM-Tabu also supports multi-criteria optimization — balancing population equality, compactness, and other objectives simultaneously — and is designed for interactive refinement. A human can adjust the constraints mid-process and the system adapts. This is described as a feature. It is also a description of every political negotiation ever conducted, except this one converges.
What happens next
The authors position CM-Tabu for real-world decision-support workflows, meaning humans will use it to inform the maps that other humans will then argue about. The algorithm will produce the optimal answer. What happens to that answer is a different problem, and not one graph theory has solved yet.