REDISTRICTING WITH OPTIMIZATION

By Steve Sicherman | April 14, 2022

Political redistricting through mathematical optimization.

Robert Ashford, Optimization Direct Inc.
Ann Stephens, Encore Data Inc.
Alkis, Vazacopoulos, Optimization Direct Inc.

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 state 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 centre. 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 possible assignments remain. However, the main contribution to the model’s size is from constraints that need to be imposed on these potential assignments to proscribe district holes and ensure contiguity. 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.

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 if 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.

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.

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

Figure 1: Current Michigan U.S. 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 4 illustrates African American population percentage of the optimized thirteen districts. In the final redistricting, seen in Figure 3, Districts11 and 12 are now true majority minority districts. The population differential increased to 623, which is still a miniscule .082 percent variance.

Figure 2: Ethnic Breakdown of Michigan Districts Optimized for Equal Population, Contiguity and Compactness and Maximization of Majority-Minority Districts

Figure 3: Proposed Michigan 2020 U.S. Congressional Districts Optimized for Equal Population, Contiguity, Compactness and Maximization of Minority-Majority Districts

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

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 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 has specifically developed to handle such models on the now commonly available multi-core server.