Re: [Help-glpk] Time Limit Didn't Work On Tournament Model

[Michael Hennebry]

On Sat, 5 Sep 2009, Tawny Owl wrote:
> btw - can anyone offer any advice has to how to break the symmetry in this 
> problem, please? I previously modelled it to solve to all pairs of teams having 
> at least one opponent in common, and used the objective function to break the 
> symmetry - which worked, and produced solutions much more quickly. However, I 
> have now amended the model to cover team/round permutations in which it is not 
> possible to ensure that all pairs of teams have an opponent in common - in 
> which case, the aim is to minimise the cases of pairs of teams having no 
> opponent in common.

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.
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.
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:
j in 1..12, k in j+2..14, k != j+1, 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   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."