Optimal Political Districting by Implicit Enumeration Techniques
作者： R. S. Garfinkel , G. L. Nemhauser
关键词: Redistricting 、 State (functional analysis) 、 Compact space 、 Contiguity 、 Mathematics 、 Set (abstract data type) 、 Mathematical optimization 、 Population 、 Enumeration 、 IBM
摘要: An algorithm is given which finds all optimal solutions, for a set of criteria, to political redistricting problems. Using “population units” as indivisible elements, the first phase generates feasible districts, where feasibility indicates contiguity, compactness and limited population deviation. The second that M districts “covers” each unit exactly once, minimizes maximum deviation any district from mean population. Computational results indicate states with 40 counties or fewer can be solved in less than 10 minutes on an IBM 7094. However, our attempt solve 55 county state was unsuccessful.
acm.org
sci-hub.se 参考文章(7)
S. W. Hess, J. B. Weaver, H. J. Siegfeldt, J. N. Whelan, P. A. Zitlau, Nonpartisan Political Redistricting by Computer Operations Research. ,vol. 13, pp. 998- 1006 ,(1965) , 10.1287/OPRE.13.6.998
M. L. Balinski, Integer Programming: Methods, Uses, Computations Management Science. ,vol. 12, pp. 253- 313 ,(1965) , 10.1287/MNSC.12.3.253
R. S. Garfinkel, G. L. Nemhauser, The Set-Partitioning Problem: Set Covering with Equality Constraints Operations Research. ,vol. 17, pp. 848- 856 ,(1969) , 10.1287/OPRE.17.5.848
John F. Pierce, Application of Combinatorial Programming to a Class of All-Zero-One Integer Programming Problems Management Science. ,vol. 15, pp. 191- 209 ,(1968) , 10.1287/MNSC.15.3.191
Arthur M. Geoffrion, Integer Programming by Implicit Enumeration and Balas’ Method Siam Review. ,vol. 9, pp. 178- 190 ,(1967) , 10.1137/1009031
M. L. Balinski, R. E. Quandt, On an Integer Program for a Delivery Problem Operations Research. ,vol. 12, pp. 300- 304 ,(1964) , 10.1287/OPRE.12.2.300
James D. Thoreson, John M. Liittschwager, Computers in behavioral science. Legislative districting by computer simulation Behavioral Science. ,vol. 12, pp. 237- 247 ,(1967) , 10.1002/BS.3830120309