World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special issue on Graph and Combinatorial Optimization for Big Data Intelligence with Parallel Processing; Guest Editors: Xiaoyan Zhang, Eddie Cheng, Longkun Guo and Yaping Mao)No Access

An Exact Solution Method for the Political Districting Problem by:0 (Source: Crossref)

    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.

    Communicated by Eddie Cheng


    • 1. W. Vickrey, On the prevention of gerrymandering, Political Science Quarterly 76(1) (1961) 105–110. Crossref, ISIGoogle Scholar
    • 2. F. Ricca, A. Scozzari and B. Simeone, Political districting: From classical models to recent approaches, Annals of Operations Research 204(1) (2013) 271–299. Crossref, ISIGoogle Scholar
    • 3. S. W. Hess, J. Weaver, H. Siegfeldt, J. Whelan and P. Zitlau, Nonpartisan political redistricting by computer, Operations Research 13(6) (1965) 998–1006. Crossref, ISIGoogle Scholar
    • 4. R. S. Garfinkel and G. L. Nemhauser, Optimal political districting by implicit enumeration techniques, Management Science 16(8) (1970) B495–B508. Crossref, ISIGoogle Scholar
    • 5. A. Mehrotra, E. L. Johnson and G. L. Nemhauser, An optimization based heuristic for political districting, Management Science 44(8) (1998) 1100–1114. Crossref, ISIGoogle Scholar
    • 6. S. Chopra and S. Shim, A strong formulation for the graph partition problem, Networks 75(2) (2020) 183–202. Crossref, ISIGoogle Scholar
    • 7. C. Arnold, The mathematicians who want to save democracy, Nature 546 (2017) 200–202. Crossref, ISIGoogle Scholar
    • 8. Å. Hallefjord and S. Storøy, Aggregation and disaggregation in integer programming problems, Operations Research 38(4) (1990) 619–623. Crossref, ISIGoogle Scholar
    • 9. A. P. S. Dantas, C. C. de Souza and Z. Dias, A heuristic for the convex recoloring problem in graphs, International Transactions in Operational Research (2020) 1–25. ISIGoogle Scholar
    • 10. M. Campêlo, A. S. Freire, K. R. Lima, P. F. S. Moura and Y. Wakabayashi, The convex recoloring problem: Polyhedra, facets and computational experiments, Mathematical Programming 156(1) (2016) 303–330. Crossref, ISIGoogle Scholar
    • 11. Gurobi Optimization, Gurobi optimizer reference manual, (2018). Google Scholar
    • 12. A. Hagberg, P. Swart and D. S. Chult, Exploring network structure, dynamics, and function using networkX, Tech. Rep., Los Alamos National Lab. (LANL), Los Alamos, NM (United States) (2008). Google Scholar
    • 13. Ohio Supercomputer Center, Ohio supercomputer center (1987). Google Scholar
    • 14. J. Towns, T. Cockerill, M. Dahan, I. Foster, K. Gaither, A. Grimshaw, V. Hazlewood, S. Lathrop, D. Lifka, G. D. Peterson, R. Roskies, J. R. Scott and N. Wilkins-Diehr, XSEDE: Accelerating scientific discovery, Computing in Science and Engineering 16(5) (2014) 62–74. Crossref, ISIGoogle Scholar
    • 15. S. Chopra, H. Park and S. Shim, Extended graph formulation for the inequity aversion pricing problem, INFORMS Journal on Computing 34(3) (2022) 1327–1344. Crossref, ISIGoogle Scholar