An exact method for the political districting problem

Mehrotra, Johnson, and Nemhauser (1998) [Management Science 44, pp. 1100–1114] addressed a problem for political districting and developed an optimization based heuristic to find good districting plans which partition the population units into contiguous districts with equal populations. Their case study found a good South Carolina plan at a penalty cost of 68. This paper develops a strong integer programming model identifying the exact optimal solution. Our model identifies the optimal South Carolina plan at the minimum penalty of 64. Motivated by the 2019 lawsuit challenging the congressional plan as gerrymandering, we inspect the actual Maryland plan.