[EM] District continuity preserving re-districting

[Ernest Prabhakar]

On Mar 14, 2004, at 7:37 PM, Niemzinski at ecybermind.net wrote:
> I don't know how to simultaneously combine two different optimization 
> goals like
> # lanes of traffic cut and population moment of intertia, let alone 
> adding a
> third such as population transfers.  My assumption is that we can only 
> optimize
> on a single goal so all other goals within the optimization model must 
> be
> represented as constraints

Not really, if you're willing to use a non-deterministic optimization 
algorithm.

For large parameter space problems like this one, I prefer "simulated 
annealing."   In this case, one starts with an arbitrary (random) 
solution and perturbs it until it reaches a local minima.  To help it 
try to find a global (or at least semi-global) minima, the system 
'jumps' around, in such a way that value-increasing jumps are less 
likely than value-decreasing jumps.

What this means is that one can define a function to be minimized like:

V =  (S/dS)^2 + (T/dT)^2

dS, then, corresponds to some measure of uncertainty, e.g., the 
standard deviation expected of S.  Essentially, we are saying that 
fluctuations of size dS are unimportant.  Put another way, fluctuations 
of size dS in S are equivalent to fluctuations of size dT in T.

To pick one example, population fluctuations are usually characterized 
by an uncertainty of sqrt(N), so one term might be (N1-N2)/sqrt(N1).

The transition probability from state 1 to state 2 goes like 
(S12/dS)^2, where S1 - S2.  The overall transition probability is the 
sum of squares (suitably normalized).

I probably missed a square or sqrt(2) somewhere, but  hopefully you get 
the idea.  As long as one can determine the appropriate dS, one can 
easily add as many variables as one wants to the simulation.  Of 
course, that increases the complexity of the space, so you'd need more 
runs to find a nearly-optimal solution.

Another option is to use one set of criteria for the minimization 
process, and another for the evaluation after the fact.

Hope this is helpful, or at least interesting.

- Ernie P.