Political Districting and OR

When I think about how Operations Research can contribute to the world of politics, one of the first things that come to mind is the redistricting process which, of course, has been receiving a lot of attention after the 2010 census. Here’s an excerpt from the census.gov web site:

Another major use for decennial census data is for geographically defining state legislative districts, a “redistricting” process that begins in 2011. The census data allow state officials to realign congressional and state legislative districts in their states, taking into account population shifts since the last census and assuring equal representation for their constituents in compliance with the “one-person, one-vote” principle of the 1965 Voting Rights Act.

One of my favorite articles on the topic is “An Optimzation-Based Heuristic for Political Districting” by Anuj Mehrotra, Ellis Johnson and George Nemhauser, which appeared in Management Science in 1998 (henceforth referred to as the MJN paper). For a districting plan to be acceptable, it has to be fair/unbiased (to avoid gerrymandering), where fairness can be defined in terms of criteria that districts have to satisfy, such as population equality, contiguity, and compactness. Contiguity means that the district cannot have holes in it. Compactness is a bit more difficult to define, but it essentially means that districts should look more like a circle or square than like a snake or a tree branch. For example, would you say that this state senate district in Florida is compact?

Another important issue is that the methodology used to create the districts be transparent. This is a strong point in favor of using mathematical techniques such as those of Operations Research. The algorithm and software code used to create the districts can be made publicly available for anyone to inspect. Specific questions about the methodology can be answered precisely and unambiguously. There’s no beating around the bush. I applaud efforts such as the Public Mapping Project, which attempts to make the districting process more transparent and increase public participation. Nevertheless, given how difficult the problem is (in both practical and mathematical terms), I believe that it would also be important to consider plans created with the help of OR. As no mathematical model is perfect, those plans will probably need to be fine-tuned by a human being using tools such as this district builder. Of crucial importance, however, is the need for clear rules to guide such modifications. When is it OK to move part of a district’s border? by how much? etc. Given that current OR software tools are capable of producing multiple high-quality solutions at the end of a run, perhaps an even better alternative is to present the decision makers with a myriad of OR-generated and man-made plans, and let them pick the most adequate one. This practice is common in sports scheduling, where the leagues typically ask schedulers to provide them with many alternative solutions to choose from.

At this point, I’d like to switch gears and explore the districting problem in more detail from an OR point of view (using some ideas from the MJN paper). Districts are made up of smaller geographical units, for example counties (or pieces of counties). For illustration purposes, if a state like Ohio, which has 88 counties, is creating 18 congressional districts and those districts are to be made up of counties only, the potential number of distinct districts is

That number is greater than the number of miles I’d cover if I could travel at the speed of light for 400,000 years! (Without a bathroom break!) Obviously, many of those districts are not legitimate because they violate contiguity and/or compactness constraints. However, even if those invalid districts are eliminated, the remaining number of possible districts is still very large. Ideally, however, we’d like to use district building blocks that are much smaller than counties, such as zip codes, but that is still very challenging (and would increase the above number even more!). In the MJN paper, the authors create an initial plan using counties as building blocks and then fine tune the districts’ borders to equalize populations. Here are the “before” and “after” districting plans for South Carolina:

Pretty good improvement, huh? Their basic methodology is to associate one decision with each potential district indicating whether or not it is part of the final plan (a binary variable). The optimization model then selects a subset of the districts that covers each county exactly once (a set partitioning problem). Because the number of variables is huge (as we’ve seen above), they resort to a technique called branch-and-price. In short, branch-and-price solves an optimization problem by considering only a subset of its variables at a time and by adding in promising variables little-by-little as the search progresses. It’s possible to define mathematically what a missing “good” variable is, and to construct one (i.e. a new district) on-the-fly. During this process, many set partitioning problems have to be solved. Because these intermediate problems are not always solved to optimality, the final solution obtained in MJN, albeit very good, isn’t technically an optimal solution, and that’s why they use the word “heuristic” in the title of their paper.

Acknowledgment: I’d like to thank Brady Hunsaker for providing a nice collection of links in the comments section of this blog post by Michael Trick.

Update: Here is another post I came across this week that also talks about using OR for political districting.

• Solving for the best congressional redistricting solution in Texas (via @iamreddave on Twitter)