An Optimization Based Heuristic for Political Districting
从非政治视角出发，提出一种基于优化的启发式方法，将选区划分建模为约束图分割问题，并开发了分支定价求解方法，以美国南卡罗来纳州为例验证了满足一人一票、紧凑且连续选区原则的可行性。
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.