AN OPTIMIZATION-BASED HEURISTIC FOR POLITICAL DISTRICTING

Redistricting, the redrawing of congressional district boundaries with in 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 add ress this problem from a nonpolitical viewpoint and present an optimiz ation based heuristic incorporating universally agreed upon characteri stics. We model the problem as a constrained graph partitioning proble m and develop a specialized branch-and-price based solution methodolog y. We demonstrate the feasibility of our methodology by showing how to satisfy the one-person, one-vote principle with compact and contiguou s districts for the state of South Carolina.