[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Michael Hennebry
Subject: Re: [Help-glpk] Time Limit Didn't Work On Tournament Model
Date: Tue, 8 Sep 2009 12:18:13 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

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."

reply via email to

[Prev in Thread] Current Thread [Next in Thread]