Ernest Prabhakar wrote: I don't think that such an algorithm is actually well-defined. I believe you'd need some sort of initial conditions, and if you didn't specify them explicitly then they'd be determined implicitly by the way you ran the algorithm. And any sort of random initial conditions would tend to lead to strange boundaries. Which may not be any worse than now, but as pointed out earlier in this thread people like the idea of districts that represent 'their' community.
This raises the question of whether it is possible to come up with a reasonable initial condition for your boundary-minimization algorithm, without allowing much room for political jiggering. My best guess would be to treat this is as a crystallization problem, where the goal (constraint) is to get 'grains' of equal size and minimal boundary. The most objective initial conditions, I would think, are to have initial grains for each existing political unit (village, city, county, etc.). This would lead to some grains with 'holes', but that's just an internal boundary which would also need to be minimized. Another option would be to follow 'topographical' lines on the demographic chart (e.g., follow natural population concentrations, rather than the political boundaries). The algorithm would need two passes. In the first, it would attempt to coalesce individual grains in such a way as to minimize variance. This would probably be best done via some sort of genetic algorithm or simulated annealing, to try out various options to find out which is minimal. http://www.npac.syr.edu/REU/reu94/ramoldov/proposal/section3_2.html Matt responds: There are algebraic process for obtaining an initial feasible solution for a given integer program model. I don't know if it is possible to use initial conditions to significantly change the probability that the outcome will be favorable or unfavorable to a particular political party or candidate. But it is easy enough to formalize the process of obtaining an initial feasible solution so that it is well defined and not subject to politically motivated manipulation. I don't enough about the other optimization methods such as simulated annealing and genetic algorithm to comment on them. I don't care what method is used. Ernest Prabhakar wrote: The second phase - after roughly-equal grains (districts) have been created - would be to adjust the boundaries to both minimize circumference and decrease variance. This could probably use a more deterministic algorithm, rather than the probabilistic one above. We could even add in an extra 'cost' for moving boundaries in a way that don't fit 'natural' demographic boundaries. Matt responds: Integer programming is a deterministic optimization method. Constraints to ensure that the districts are contiguous, have no interior holes, and collectively cover the entire map are required. For interior holes, maybe lines between pairs of boundary points for a given district can be checked to verify that the lines are fully contained in the district (I am assuming that a two dimensional array is used to represent locations on the map). For collectively covering the entire map all of the array can be checked to verify that it is assigned to one and only one district. For contiguity, all the district border locations can be checked to verify they are either map boundary locations or adjacent to boundary of another district. If these constraints cannot be implemented within an integer program then it won't work. I have no comment regarding adding extra costs to try to encourage some outcome. That is another topic. ---- Election-methods mailing list - see http://electorama.com/em for list info
