[EM] Integer program for River clustering

[Kristofer Munsterhjelm]

And here, to show that it can be done, is a mixed integer linear program 
for clustering using River. River turns out to be easier to implement in 
this way than Tideman is, and River enjoys properties that Tideman 
doesn't, so I get two birds with one stone.

However, it's completely impractical for large councils. My computer and 
GLPK solver manages three or four seats in less than a few minutes, but 
then the time goes up by *a lot*.

It might be possible to use these methods in a semi-sequential manner: 
do three seats at a time (four clusters, where the last cluster just 
contains voters not assigned to any of the other clusters, not 
representing any winners so far). Determine the three winners, then 
remove the voters that have been assigned to any of those clusters. 
Repeat for the next three clusters with the candidates that have already 
been assigned disallowed (unless this is party list), and repeat until 
all the winners have been determined.

However, due to only considering three "active" clusters at a time, such 
a method might not be quite as proportional as desired. The minimax 
integer program might be more desirable, since it can get up to ten or 
fifteen seats before unacceptably slowing down. Minimax not being 
cloneproof may end up being an acceptable cost for being able to do more 
seats at once. I wouldn't know, but it's worth thinking about.

Also, these clustering methods are in the spirit of least remainder 
methods (since they have absolute quota constraints). As I mentioned 
earlier, the "spirit of Sainte-Laguë" would be more to accurately 
represent (more fair than random) something... but I'm not sure what 
that something would be. Accurately represent a random pick from all 
clusters? I don't know.

I've attached two copies. They differ in what examples they use; both 
are taken from Steven Eppley's page about independence of 
Pareto-dominated alternatives, 
http://alumnus.caltech.edu/~seppley/Independence%20from%20Pareto-dominated%20Alternatives.htm 
.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: river.mod
Type: audio/x-mod
Size: 9550 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20140215/c0b1a53d/attachment-0006.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: river_bpexamp.mod
Type: audio/x-mod
Size: 10987 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20140215/c0b1a53d/attachment-0007.bin>