[EM] Integer program for Minmax clustering

[Kristofer Munsterhjelm]

With all the recent posts about clustering methods, I thought I would 
find out if I could create a minmax clustering program. I finally 
managed to do so, albeit it currently only really works with full 
ranking (since its election mode is "pairwise opposition" at the 
moment)[1]. It is also quite slow. Even with my simple example, it takes 
a really long time to finish in party list mode for 15 seats and 
greater. Finally, there's no guarantee it breaks ties in a fair manner - 
there's no explicit tiebreaking code in there.

Still, it could be useful, and it *does* show that a Condorcet version 
of Monroe's method is possible, so I'll attach it. It's in AMPL format 
and needs a MIP solver (like the one in the GNU Linear Programming Kit) 
to be run.

The strategy is that each cluster has a minwinner number for each 
candidate, where that number is forced to be the least victory for that 
candidate in the cluster. Constraints then further force the system to 
pick only one of these as winners, and that is used in the objective 
function to be maximized.

Again, there is significant room for improvement. The program could 
possibly be altered to use an advanced method[2] instead of minmax, or 
at least to use margins instead of PO (to avoid certain problems I have 
mentioned before).

-

[1] There are two reasons as to why the better Condorcet rendering 
methods aren't used here. First, implementing wv in a linear program is 
hard (without using more integer-only parameters, which are usually 
expensive in terms of considerably slowing down solution time). Second, 
the way minmax has been handled here, it's plain old minmax, not 
"ext-minmax" (leximin-max). Thus all the zeroes in wv would make every 
candidate tie. Margins might be easier to implement, but I got weird 
results when I tried.

[2] Here I'm thinking of River in particular. It would be easier to 
implement than Schulze, it's probably quicker than Ranked Pairs when all 
we need is a winner, it's cloneproof and all those nice things, and we 
get ISDA without any additional effort compared to Ranked Pairs.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: minmax_cluster.mod
Type: audio/x-mod
Size: 4428 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20140210/041984ae/attachment-0003.bin>