[EM] Algorithmic redistricting: practical or not?

[Andrew B Jennings (elections)]

Kristofer,

Are you using actual geography and population data from somewhere?

I got involved in a similar project recently. I met with some people who want to propose computer-based redistricting for the city I live in (Mesa, Arizona, USA).

I do like the argument of Brian Olson (bdistricting.com) to use a metric-based approach instead of mandating a specific algorithm. I'm not especially concerned whether an optimal solution is tractable. I convinced those I was talking with that we could define a mathematical compactness metric and then allow public submissions (in addition to a city-proposed one) and choose the best one according to the metric. Now I just need to make sure I suggest to them the right metric! Ideally, we would set the quality metric that had zero tunable parameters, but I'm not sure that's possible.

Our city touches 6000 populated census blocks or 333 populated block groups or 137 populated census tracts.

I feel like the census tracts are too coarse to allow a good solution. The blocks seem too small, so my first attempt has been with the block groups. (Though I note that the current districts split block groups in a couple places.) I don't feel like the districts have to have equal population to within 1 person. The group I was talking with thought 3% was reasonable. That was before they knew that the current districts have a population discrepancy of 8% between the largest and the smallest. (That is from my analysis based on the 2020 census and the maps. There may be some more official calculation where the discrepancy is smaller.)

I wasn't planning on mandating convexity, though I hope the right compactness function would favor it as much as possible. I was also hoping that contiguity would come for free. It's probably not acceptable to have a non-contiguous map. Maybe we will need to say that we'll accept that best map (according to the compactness metric) that also preserves contiguity.

Olson is promoting as a metric "lowest average distance over all people to the geographic center of their district". I think he's using census blocks. Not sure if he's mandating contiguity, or what level of population discrepancy is tolerated.

Like you, I am leaning toward using the square of distance. I know I said I don't care about tractability, but it's just so much easier to compute without the square roots. It is also what is minimized when finding any geometric centroid, so it seems defensible.

Also the sum of (population weighted) squares of distances to the centroid is basically equivalent to the sum of squares of distances between every pair, which feels elegant. And it can be converted into "for every pair of block groups, there is a cost whenever they are in the same district" max-cut graph problem. Alternatively, it makes naive brute-force searching much faster.

Taking that metric (sum of squares of distances) and finding local minima gives good looking districts, but they vary in population by 200% or more. I doubt that brute force or MILP optimizer can get it down to 3-8%, but I'm going to keep trying things.

I have tried a couple other things with the cost function:

1. Instead of using the distance between the census-given "interior point" of each block, use the distance between the closest points for each pair of blocks.

2. A penalty for uneven district sizes (add to the cost function a large constant times the population of both block groups in the pair)

I can tune the constant to get population discrepancies down to 3-8% and districts that are almost contiguous, although I hate having a constant that can be tuned by politicians. Maybe I can find some way to formulate it based on city population, city geography, and the number of districts, or something.

Or maybe I just need to try using the 6000 census blocks and see what happens.

~ Andy Jennings




On Tuesday, February 4th, 2025 at 2:39 PM, Kristofer Munsterhjelm <km-elmet at munsterhjelm.no> wrote:

> 
> 
> So I got myself entangled in redistricting back in November, after
> writing a post here about how solving a related problem (that I thought
> was the same as districting) could be done through linear programming,
> if the centers were given.
> 
> Some months and lots of code later, I thought I'd post about what I
> found out.
> 
> The summary, first:
> - Bad news: the linear program I gave doesn't ensure contiguity or
> convexity, and my attempts to forcing it were too expensive.
> - Good news: the linear program isn't useless and can be used as a
> component in a branch-and-bound-like approach. Once it has found a good
> choice of centers, a local search can be used to find a convex solution.
> - All of this is much harder than just using proportional
> representation, so it's mostly an intellectual exercise.
> 
> 
> To recap, the linear program is:
> For centers i = 1...n, with cneterx_i, centery_i being the (x,y)
> coordinates of center i
> 
> minimize the sum over centers i, and points x, y inside the state:
> (1) assign[i, x, y] * (pop(x, y) + eps) * dist^2(centerx_i,
> centery_i, x, y)
> 
> subject to
> (2) for all i, x, y: 0 <= assign[i, x, y] <= 1
> (3) for all i: (sum over x, y: assign[i, x, y] * pop(x, y)) - tpop/n = 0
> (4) for all x, y: (sum over i: assign[i, x, y]) = 1
> 
> (1) defines the problem: minimize expected squared distance from a
> random inhabitant to their assigned center. Assign[i, x, y] is a free
> variable that is one if the point (x,y) is assigned to center i, zero
> otherwise, and pop(x, y) is the number of people at that reside closer
> to (x,y) than any other point. The epsilon value eps ensures that a
> point with no population is assigned to its closest center.[1]
> (2) defines the range of the assign values.
> (3) implements the population constraint that every district has equal
> population.
> (4) requires that every point be assigned to some district.
> 
> The linear program does solve the problem as specified. However, the
> resulting districts aren't contiguous.
> 
> You'd think they were because suppose district A picks a point that's
> inside district B, then shouldn't we be able to improve the solution for
> both by swapping this assignment with points closer to A? The problem is
> the population constraint. Sometimes it's easier to skip points because
> otherwise, a bunch of other points would have to change to keep equal
> populations, and the sum of these changes could be worse.
> 
> So instead you need additional constraints, and these are expensive.[2]
> That's the bad news.
> 
> The good news is that it's actually not as bad as you'd think, because
> the linear program I gave provides a good lower bound for a contiguous
> solution. Furthermore, with integer programming, it's possible to add a
> large number of candidate points and have the solver choose only some of
> these as centers. For instance, we may pick 150 candidate centers with
> something like kmeans++; and then use an integer program to say it
> should choose 8 of them, like this:
> 
> minimize the sum over centers i, and points x, y inside the state:
> assign[i, x, y] * (pop(x, y) + eps) * dist^2(centerx_i, centery_i, x, y)
> 
> subject to
> (2b) for all i, x, y: 0 <= assign[i, x, y] <= chosen[i]
> for all i: (sum over x, y: assign[i, x, y] * pop(x, y)) - tpop/k *
> chosen[i] = 0
> for all x, y: (sum over i: assign[i, x, y]) = 1
> (5) sum over i: chosen[i] = k
> 
> free variables: assign[i, x, y] continuous, chosen[i] binary
> 
> (2b) says: if chosen[i] is zero, then nobody can be assigned to center
> i. Otherwise, points may be assigned to center i.
> (5) forces exactly k districts to be chosen. The population constraint
> (3) has also been updated accordingly: if chosen[i] is zero, then
> population must be zero.
> 
> (Thanks to Joshua Boehme for this idea.)
> 
> When run, the program will find the best k centers and give, as its
> objective value, a lower bound on the sum of squared distances that
> we're actually interested in. If this is worse than the current record,
> we just discard the solution as it can't be better anyway; otherwise, we
> check it more closely with contiguity constraints, which will return the
> true objective value.
> 
> This seems to work reasonably well in theory, but the datrasets are much
> too large to run contiguity-constrained programs on. Instead I use a
> method from Janáček and Gábrišová[2], which uses the property that,
> suppose we start with some given centers,
> (centerx_i, centery_i) for i = 1..k
> Then there exist weights w_i so that the "ordinary" k-means clustering
> (Voronoi clustering) objective
> minimize sum over i, x, y: assign[i, x, y] * (pop(x, y) + eps) *
> (dist^2(centerx_i, centery_i, x, y) + w_i)
> 
> will ensure that the districts have equal populations. (This makes
> intuitive sense: if w_i is very large, district i is penalized and
> shrinks relative to the other districts.) And this "uncapacitated" or
> unconstrained problem can be easily solved by checking each point's
> value for each district and picking the best.
> 
> So I ended up with a two-step procedure: use integer programming to find
> reasonably good centers from a randomly selected large enough candidate
> pool, and then use a local search to update the weights w_i until the
> districts had nearly equal populations, thus enforcing contiguity and
> convexity.[3][4]
> 
> In practice, there were a bunch of additional problems due to census
> district shapes, non-Euclidean geometry, and how to handle large amounts
> of data quickly. But I won't go into those here; perhaps later, as this
> post is long enough.
> 
> -km
> 
> [1] I made a mistake back when I stated this back at the end of October:
> the objective value should be weighted by population, not just sum of
> squared distances. Otherwise every district wants to be exactly the same
> size as the others, which leads them all to carve inwards to cut shares
> of cities. See the unweighted objective picture here:
> https://github.com/kristomu/redistricter/tree/master/undesired_outcomes
> 
> [2] See JANÁČEK, Jaroslav; GÁBRIŠOVÁ, Lýdia. A two‐phase method for the
> capacitated facility problem of compact customer sub‐sets. Transport,
> 2009, 24.4: 274-282.
> 
> [3] As far as I understand, it's possible to use a postprocessing phase
> to force exact equality. The Janáček and Gábrišová paper gives more detail.
> In my tests for Colorado, the local search converged to around 0.02%
> difference in population between the most populated district and the
> least, so I didn't implement it.
> 
> [4] There may be better ways to find the weights than local search, see
> e.g. SPANN, Andrew; KANE, Daniel; GULOTTA, Dan. Electoral redistricting
> with moment of inertia and diminishing halves models. The UMAP Journal,
> 2007, https://rangevoting.org/SpannGulottaKaneMCM2007.pdf, particularly
> pages 9 and 10.
> ----
> Election-Methods mailing list - see https://electorama.com/em for list info