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

{88 \choose 18} = 2,\!418,\!561,\!960,\!739,\!869,\!780

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.



Filed under Applications, INFORMS Monthly Blog Challenge, Integer Programming, Modeling, Motivation, Politics, Promoting OR

9 responses to “Political Districting and OR

  1. The flaw here is that “fairness” is defined (by the party in power at the time of redistricting) as “keeps our seats safe for the indefinite future”. So perhaps a more practical model would minimize the geometric goofiness of districts with a side constraint that the incumbent party should retain at least as many “safe” districts as they currently own. (Not that I’m being cynical or anything.)

  2. orbythebeach

    Paul: Thanks for the comment. I agree that all kinds of cheating strategies are applied, but the (my) hope is that, by using an OR model, the definition of fairness would have to be made explicit and precise, and perhaps we’d get a bit closer to actual fairness.

  3. Robert

    Here is a link I saw a long time ago about another approach
    to redistricting designed by a mathematician.
    http://rangevoting.org/SplitLR.html Haven’t looked at in depth but
    it seems more geometrically inspired.

  4. orbythebeach

    Robert: thanks for the link. I’ll check it out.

  5. @Tallys: I’m sympathetic to the desire for transparency,
    but my strong suspicion is that any redistricting method that
    actually is fair has no chance of being adopted, since adoption
    requires approval by the very people who benefit from unfairness.
    The one hope would be judicial intervention to require a truly fair
    algorithm, but I’m not sure the judiciary would have grounds to

  6. I think Paul Rubin and I agree on most everything. But I would add that it doesn’t take OR (now called “Business Analytics” by the way) to tackle the problem. It just takes a ruler, either the kind that dictates (like a strong governor) or the measuring stick kind. Draw a square or rectangular boundry no more than x miles around a district and adjust for geography, like rivers. We, in Florida, have the most aggregious district around—it runs from Jacksonville to Orlando, at some places just the width of I-4. It will be interesting to see if it ever gets changed.

  7. orbythebeach

    Barry: thank you for the comment. The distinction between Business Analytics and OR will vary from person to person, depending on how you define OR. For example, some people would say that Statistics is part of OR, but that’s not a universal belief. For an interesting point of view on the distinction between Analytics and OR, see the comment by Michael Rappa on this blog post. I certainly agree that it’s easy to come up with a feasible solution manually by just looking at the map, but I still believe that using an optimization model can bring you closer to satisfying criteria like population equality with a lot less trial-and-error. Of course, as Paul correctly pointed out, this is one of those problems in which the decision makers are biased against the mathematically ideal optimal solution. Nevertheless, I still enjoy having this kind of discussion because it highlights the pros and cons of the mathematical approach and helps increase the visibility of our field.

  8. I have another reading on the morphing from OR to analytics. You can see my blog of a few days ago at http://www.heizerrenderom.wordpress.com. There are many reasons why the change is needed, and you are 100% correct re stat and the differing views people have (which is, of course, one of the reasons we have a problem in our profession).

  9. Burçin Bozkaya

    I also read this article and I, myself, have academic and practical experience in use of OR in political districting. I agree that the key issues are fairness (or objectivity) and transparency. When I mention to people that we have algorithms for automated districting, I instantly get a feedback that these are suitable only for other types of districting, not for political districting. Being an OR professional myself, I think otherwise, as OR methodologies, if they can fully (or near-fully) capture the governing rules and they are also transparent, can form an objective framework where few can claim that there is deliberate gerrymandering or other manipulations.

    In our recent project with the City of Edmonton in Canada for city council election districting, we applied a heuristic multi-criteria algorithm (that originated from my PhD thesis) integrated with ArcGIS. Using this approach, it is possible to quickly (in a matter of seconds) generate good quality maps that appeal to different tastes (using adjustable weights on multiple criteria). The city officials would in fact take this as their first step and then modify the map as they see fit. But in our experience, the number of modifications were so minimal that we were convinced the algorithm can successfully address most, if not all, of the relevant districting requirements. This work will be published in Interfaces soon. An earlier work of ours was published in EJOR.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s