Gerrymandering is a problem in the USA, and has led to notable Supreme Court cases in recent years. Examples include:
- Lamone v. Benisek, regarding Democratic gerrymandering in Maryland;
- Rucho v. Common Cause, regarding Republican gerrymandering in North Carolina;
- Abbott v. Perez, regarding racial gerrymandering in Texas.
To deal with these issues, reformers have sought to change who controls the redistricting process, or what rules redistricting plans should follow. Constraints on traditional redistricting principles (e.g., population balance, contiguity, compactness, preservation of counties or other political subdivisions) are thought to prevent the most egregious of gerrymanders.
But, at what point do these constraints make redistricting impossible?
Here, we consider one of the most basic questions in redistricting: Can my state draw its congressional districts so that:
- all districts have roughly the “same” population;
- each district is contiguous on the map; and
- no county is split between districts?
The Input Data
To define the problem, we need some input data:
- k : the number of districts to draw
- L : the fewest number of people allowable in each district
- U : the most number of people allowable in each district
- p(i) : the number of people in county i
- V : the set of counties
- E : the pairs of counties that are adjacent
- G=(V,E) : the contiguity graph (or “network”)
For example, Oklahoma has 77 counties that should be partitioned into k=5 congressional districts. After the 2010 census, Oklahoma’s population was 3,751,351, so each district should have roughly 750,270.2 people in it. We will allow a little flexibility and require each district to contain between L=746,519 and U=754,021. This ensures that the most and least populated districts will differ by at most 1%. The total number of county adjacencies is 195. An example is Oklahoma County and Cleveland County.
The data for all 50 states can be found here.
An Initial MIP
We start with a classical optimization model that goes back to the 1960s. It will enforce the most basic constraints in redistricting. It uses decision variables of the form:
x(i,j) = should county i be assigned to the district centered at county j?
If so, then x(i,j) should equal one. Otherwise, it will be zero. The MIP is given by:
Constraints (1b) ensure that each county i is assigned to one district. Constraint (1c) ensures that there will be k districts. Constraints (1d) ensure that each district has population between L and U. Constraints (1e) ensure that counties can only be assigned to a district that exists. Constraints (1f) ensure either that county i is assigned to county j or that it is not. The objective function (1a) that is being minimized seeks “compact” districting plans. Ultimately, this will be unimportant for us, as we’re only interested in determining whether there is a feasible districting plan, not whether it is “compact”.
For computational niceties, we require each district to be “centered” at its most populous county. This can be achieved by fixing x(i,j)=0 when county i is more populous than county j. This changes the objective value of model (1), but not its feasibility status.
We see that most states cannot redistrict at the county level. A primary reason is large cities. For example, Dallas County in Texas had a population of 2,368,139 in 2010, which far exceeds the bound U that we imposed. We call such instances “overtly infeasible”.
There are also seven states that are “trivial” in the sense that only one congressional district should be created and it must cover the whole state. There is nothing to solve.
There are 16 states left. When running the code, we see some problems. For example, here is a solution for Oklahoma:
Obviously, this districting plan lacks contiguity. This should not be a surprise; we never imposed contiguity constraints in our MIP!
Adding Contiguity Constraints
There are many ways to add contiguity constraints to our MIP. In the example python code, we use the simplest approach, which is based on flow techniques. Intuitively, the idea is to create flow at each district’s center and send it along the district’s edges to fuel the district’s other nodes. For the details, see model (2) here.
With these constraints, our issue for Oklahoma has been fixed.
Our computational results tell us that there is no solution for Colorado, New Hampshire, Oregon, or South Carolina.
By looking at the Denver and Portland metros below, can you see why?
If you’re looking for a harder puzzle, see if you can figure out why South Carolina cannot redistrict at the county level.
The other twelve states *do* admit contiguous county-level solutions: Alabama, Arkansas, Iowa, Idaho, Kansas, Louisiana, Maine, Mississippi, Nebraska, New Mexico, Oklahoma, and West Virginia. Try to draw some of them for yourself at districtr.org.
Only two states—Iowa and West Virginia—drew county-level maps after the 2010 census (if we exclude states with one congressional district). Based on the analysis conducted here, at most 10 other states could follow.
I emphasize “at most”, because our analysis does not consider all federal and state laws. For example, Section 2 of the Voting Rights Act (as interpreted by the Supreme Court in Thornburg v. Gingles) requires the creation of minority opportunity (or “majority-minority”) districts in certain cases. Preliminary analysis suggests that, when this constraint is considered, Alabama cannot redistrict at the county level.
My coauthors Hamidreza Validi, Eugene Lykhovyd, and I wrote a paper about handling contiguity constraints in redistricting problems when the units are census tracts instead of counties. These instances are much larger than the county-level instances considered here and require alternative MIPs and advanced techniques, like branch-and-cut algorithms and Lagrangian-based reduced-cost fixing, to solve in a reasonable amount of time. Here are links to that paper and code.