Redistricting with Optimization

Introduction

The US Census Bureau conducts a full census of all states in the USA every ten years. When the data is collected, collated, checked and released it must be used to redistrict each sate for the election of representatives to the US Congress, State Senate and State House. This is an expensive and politically fraught process often involving significant litigation. Gerrymandering is commonplace and causes political disquiet in its undermining of the democratic process.

We propose to use optimization to accomplish these redistricting tasks. For each state these assignment problems can be formulated as a Mixed Integer Programs (MIPs) [1]. The MIP ensures district contiguity, minimizes district diameter and attempts to balance district population size. Furthermore it needs to ensure compliance with the Voting Rights Act (1965 and renewed) in that if a district with a majority of a minority group can be created, it should be.

The MIP models are necessarily very large and challenging even for a state like Michigan which is by no means the most populous. We use ODH|CPLEX from Optimization Direct Inc. and IBM Corp. as a tool for solving these models. Typically it ensures that district population deviation from the average is less than half a percent and that the districts are appropriately shaped – without holes, not winding and generally compact.

The merit of this method is that it is entirely non-political having no Republican or Democrat bias whatsoever. It is both transparent and auditable. It is configurable in that it can reflect state priorities in trading, for example, district diameter off with population balance.

Methodology

Each redistricting task is an assignment problem in which each of a large number of indivisible voter tracts need to be assigned to one of a much smaller number of districts. Voters in a district elect a representative for the US Congress, State Senate or State House according to the redistricting task. The assignment must yield districts which are approximately equally sized in terms of population, contiguous, without holes and compact.

There are between 132 and 8057 voter tracts in a state depending on its population size (2010 Census). The number of districts varies from 1 (congressional district in Wyoming) to 400 (for the State House in New Hampshire). Typically there are around 2813 voter tracts, 13 congressional districts, 38 State Senate districts and 110 State House districts (for Michigan, 2010 Census).

Because the geographical position of the voter tracts needs to be considered, we allow every voter tract to be a potential district center. Thus in the case of Michigan, e.g. there are potentially 7.9 million combinations that need to be represented. Removing implausible assignments reduces this by 60% – 90% depending on the model so, e.g. in the case of Michigan’s congressional districting, only about 2.7 million plausible assignments remain. However, the main contribution to the model’s size is from constraints that need to be imposed on these potential assignments to ensure contiguity and proscribe district holes, such as a donut shaped district with others in its center. Their number depends the state’s physical geography but is typically around 65 for every potential assignment.

Technically this is a multiway number partitioning problem [4] with side constraints. It has received some attention in the technical literature: [5] is fairly comprehensive: it reviews and refines formulations and algorithms for the districting problem but the methods are not readily auditable, since special-purpose algorithms need to be used to handle an otherwise impractical number of constraints. It does not proscribe holes and whilst the majority-minority issue is recognized, it is not addressed in the numerical experiments. The authors state their intent only ‘to compare the performance of the contiguity formulations on realistic instances—and not to create “good” plans’.

We perform the optimization in two stages. In the first we minimize a weighted combination of the maximum population deviation of the districts and the sum of the district diameters and ignore the voter tract ethnic composition. In the second, we account for the ethnic composition of the voter tracts and constrain the district population deviation, minimizing the weighted sum of the district diameters and penalties for minority-minority districts.

Weights and the population deviation constraint can be chosen to capture the state’s priorities and goals in this task. For example, we would normally use a population deviation constraint of 0.5%, but the population deviation can usually be reduced to 0.05% or less at the expense of less compact districts. Sates can also prioritize not splitting counties across congressional districts.

The MIP models are very large – typically around 80M constraints, 1.3M variables (nearly all of which are binary) and 160M matrix elements. Just solving the root LP of the MIP can take 12 or more hours with IBM ILOG CPLEX 20.10 [2] running on a 24 core Intel Xeon server. To get solutions we used Optimization Direct’s ODH|CPLEX 6.05 [3] solver which can find solutions whilst the underlying CPLEX solver tightens the dual bound. The solution to the first model is used as a starting solution for the second.

An Example: Michigan’s Congressional Districts

We chose Michigan as a test example using the 2010 Census data for the following reasons:

• It is reasonably large.  With a population of 10,077,331 it is the 10th largest U.S. state.
• It is reasonably diverse.  Michigan has an African American population of nearly 15%, fairly similar to that of the U.S. as a whole.
• It has strong liberal and conservative factions.  Michigan has significant urban and rural populations, which traditionally vote for the Democratic and Republican parties respectively.
• It is serious about ending gerrymandering.  Michigan has recently established an Independent Citizens Redistricting Commission to assure its Congressional, State Senate, and State House district lines are drawn fairly.

Today’s Michigan U.S. Congressional Districts

Before we begin optimization, it is useful to review the current Michigan Congressional Districts.

Figure 1 represents the most recent U.S. Congressional map of Michigan, which was drawn from 2010 Census data by the state legislature.  Many considered the map an example of gerrymandering.  As a result, in 2017 the Michigan Democrats and the League of Women Voters jointly filed a lawsuit stating that the districts were drawn by Republicans to disenfranchise Democrats.  A panel of three Federal judges agreed, unanimously ruling that the map represented a political gerrymander “of historical proportions,” and that its’ primary purpose was indeed to “subordinate the interests of Democratic voters and entrench Republicans in power.”

The suit was appealed to the U.S. Supreme Court, where the decision of the lower court was overturned.  In a 5-4 ruling, Chief Justice John Roberts agreed that though the districts were “highly partisan by any measure,” state redistricting is “beyond the reach of the federal courts,” and that states should handle districting issues themselves.

In a parallel action, in November 2018, Michigan voters voted to create an independent Citizens Redistricting Committee, to ensure that all redistricting is performed in a non-political manner.

Optimized Congressional Districts

We used the 2010 Census Bureau population and tract data but divided it into the 13 districts needed for 2020, which represents the loss of one district from 2010.

Ignoring ethnic composition and minimizing a weighted sum of district diameters and maximum district population variance, we obtained a districting in which the district populations from this model are nearly identical.  The largest population variance is just 24 people, which represents compliance within .003 percent.

To fully comply with Federal law, the Voting Rights Act of 1965 mandates that majority-minority districts must be created whenever possible. In 2010, Michigan did not have concentrated Hispanic or Asian populations large enough to warrant a majority district. This was not true of the African American population, however, so in the second stage we constrained the maximum population variance to 0.5% and minimized a weighted sum of the district diameters and penalties for minority-minority districts.

This optimization produced two such districts.  Figure 2 illustrates African American population percentage of the optimized thirteen districts.  In the final redistricting, seen in Figure 3, Districts11 and 12 are majority minority districts.  The population differential increased to 623, which is still a miniscule .082 percent variance.

Unless other parameters were required by the Commission, this would have likely been the final 2010 Congressional Districts in Michigan as determined through optimization.

Another Example: Virginia’s Congressional Districts

Virginia is another interesting test case because of the contentious recent history of redistricting following the 2010 Census. The state legislature approved a redistricting in January 2012. It was subject to Court action over gerrymandering and racial ‘packing’ in October 2014 and June 2015. The United States District Court for the Eastern District of Virginia ordered the state to draft a new congressional district map by September 2015. The state failed to do this and so a congressional district map was drawn by a panel of federal judges for use in 2016. This was appealed to the Supreme Court of the United States in January 2016, but the appeal was denied meaning that the newly drawn map would be used for Virginia’s June 2016 primary election and November 2016 general election. Legal proceedings cost over \$8M.

In 2020 the voters of Virginia elected to create the Virginia Redistricting Commission of eight citizens and eight legislators to draw Virginia’s congressional and state legislative districts in 2021.

On the basis of the 2010 Census, the current 11 congressional districts have a maximum population deviation of 20% (13% voting age population deviation) and one majority-minority district (number 3) with 54% of the voting age population being African-American. However, there is no majority minority district in this arrangement if more recent population data are used such as the 2019 American Communities Survey. The current congressional district map is shown in Figure 4.

For comparison, we used our optimization procedure to generate a districting on the basis of the 2010 data. This is summarized in figure 5 below.

The largest population deviation is only 0.18% and there is one majority-minority district (district 4). Note that our method only aims for majority minority where possible and does not actively seek more than a 50% minority representation. This complies with the Voting Rights Act and counters notions of ‘packing’ associated with a larger majority of a minority. As with Michigan, it is not possible to create a district with a majority of Asian or Hispanic voters. The mapping of this districting is shown in Figure 6.

Conclusion

We believe that optimization is the most transparent and fair method of creating political districts. However, optimization is a highly challenging process that seeks the ideal answer to a problem with hundreds of millions of possible solutions.  The enormity of the problem can be addressed in 2021 because states like Michigan and Virginia are now seriously addressing the gerrymandering issue, while advances in computer software and hardware have made the necessary large-scale optimization possible.  The ODH|CPLEX optimizer is commercially available software that has been specifically developed to handle such models on the now commonly available multi-core server.

References

[1] Ashford, R.W. (2007), “Mixed Integer Programming: A Historical Perspective with Xpress-MP”, Ann Oper Res 149:5-17, Springer-Verlag.

[2] IBM ILOG CPLEX Optimization Studio https://www.ibm.com/uk-en/products/ilog-cplex-optimization-studio

[3] ODH|CPLEX http://www.optimizationdirect.com/

[4] Graham, Ron L. (1969). “Bounds on Multiprocessing Timing Anomalies”. SIAM Journal on Applied Mathematics. 17 (2): 416–429.

[5] Validi, H.,  Buchanan, A. and Lykhovyd, E. (2021), “Imposing contiguity constraints in political districting models”, to appear in Operations Research.