On Tue, 8 Sep 2009, Michael Hennebry wrote:
Another poster noted that not all your binary variables have to be binary. That still leaves symmetry. A lot of theorectically correct symmetry-breaking constraints don't do a lot because they don't affect the linear relaxation much. Your problem has a tremendous amount of symmetry: 4!*24! > 1.9 trillion. I think that some of it can be helped by fixing the opponents in the first round. Apparently every team plays every round. All teams are equivalent, ergo all pairings are equivalent.
Oops. I seem to have made a mess here:
Fixing the pairings selects one equivalent Let the pairings be 1:8, 2:9, ... 7:14. possiblilty out of 13*11*9*7*5*3=135135.
Fixing the pairings selects one equivalent possiblilty out of 13*11*9*7*5*3=135135. Let the pairings be 1:8, 2:9, ... 7:14.
For round 2, you can define two equivalent sets of 7 teams. Within a set, no two teams have played each other. The index sets can be 1..7 and 8..14. In what follows, I think round2[j, k] should be roundGamePair[2, j, k]. Within a set, allow only consecutively numbered teams to play and between sets, require indices differ by 7:
This could be better, also:
j in 1..12, k in j+2..14, k != j+1, k != j+7: round2[j, k]=0
j in 1..12, k in j+2..14, k != j+7: round2[j, k]=0
round2[7, 8]=0 Reserve the higher indices for cross-set play: j in 1..6 : round2[j, j+7] <= round2[j+1, j+8] After round 2, you are on your own.
-- Michael [email protected] "Pessimist: The glass is half empty. Optimist: The glass is half full. Engineer: The glass is twice as big as it needs to be." _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
