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.