An Optimization Based Heuristic for Political Districting

Anuj Mehrotra, Ellis L. Johnson and George L. Nemhauser
Additional contact information
Anuj Mehrotra: Department of Management Science, University of Miami, Coral Gables, Florida 33124-8237
Ellis L. Johnson: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
George L. Nemhauser: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Management Science, 1998, vol. 44, issue 8, 1100-1114

Abstract: Redistricting, the redrawing of congressional district boundaries within the states, may occur every 10 years on the basis of the population census. Many redistricting plans are designed with partisan politics in mind, resulting in disputes and forcing judges to intervene. We address this problem from a nonpolitical viewpoint and present an optimization based heuristic incorporating universally agreed upon characteristics. We model the problem as a constrained graph partitioning problem and develop a specialized branch-and-price based solution methodology. We demonstrate the feasibility of our methodology by showing how to satisfy the one-person, one-vote principle with compact and contiguous districts for the state of South Carolina.

Keywords: Graph Partitioning; Branch-and-Price; Column Generation; Clustering; Districting (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (56)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.8.1100 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:44:y:1998:i:8:p:1100-1114

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().