[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:59:44 -0500 (CDT) |
User-agent: |
Alpine 1.00 (DEB 882 2007-12-20) |
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 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."