|
From: | Tawny Owl |
Subject: | [Help-glpk] RE: Time Limit Didn't Work On Tournament Model |
Date: | Sat, 12 Sep 2009 13:39:42 +0100 |
Hi Michael and Xypron, Thank you both for your helpful responses! Between you, you have enabled me to crack the problem. Here's the model that now works: # make fixture list to minimise cases of teams having no opponents in common # adjust teams and rounds below set teams:= 1..14; set rounds:= 1..4; var game {i in teams, j in teams: i < j}; var roundGame {i in rounds, j in teams, k in teams: j < k} binary; var gamepair {i in teams, j in teams, k in teams: i < j and not (i = k or j = k)} >=0, <= 1; var incommon {i in teams, j in teams: i < j} >= 0, <= 1; maximize gamesInCommon: sum{i in teams, j in teams: i < j} incommon[i, j]; # fix the first round s.t. fixRound1{i in 1..card(teams) div 2}: roundGame[1, i, i + card(teams) div 2] = 1; #fix the second round #s.t. fixRound2{i in 1..card(teams) div 2}: roundGame[2, 2*i - 1, 2*i] = 1; # identify game pairs s.t. identifyGamePairs2{i in teams, j in teams, k in teams: i < j and not (i = k or j = k)}: gamepair[i, j, k] <= game[min(i, k), max(i, k)]; s.t. identifyGamePairs1{i in teams, j in teams, k in teams: i < j and not (i = k or j = k)}: gamepair[i, j, k] <= game[min(j, k), max(j, k)]; # identify opponents in common s.t. opponentsInCommon{i in teams, j in teams: i < j}: incommon[i, j] <= game[i, j] + sum{k in teams: i != k and j != k} gamepair[i, j, k]; # same number of games in each round s.t. sameNumGamesPerRound{i in rounds}: sum{j in teams, k in teams: j < k} roundGame[i, j, k] = card(teams) div 2; # particular fixture only played once s.t. gameOnceMax{i in teams, j in teams: i < j}: sum{r in rounds: i < j} roundGame[r, i, j] = game[i, j]; # no team plays more than once in a round s.t. maxOneGamePerRound{r in rounds, t in teams}: sum{i in teams, j in teams: i !=j and i < j and (t = i or t = j)} roundGame[r, i, j] <= 1; solve; printf "*** rounds ***\n"; for {r in rounds} { printf "Round %s: ", r; for {i in teams, j in teams: i < j} { printf "%s", if roundGame[r, i, j] then i else ""; printf "%s", if roundGame[r, i, j] then "v" else ""; printf "%s", if roundGame[r, i, j] then j else ""; printf "%s", if roundGame[r, i, j] then " " else ""; } printf "\n"; } printf "*** opponents ***\n"; for {t in teams} { printf "Team %s: ", t; for {i in teams, j in teams: i < j and (i = t or j = t)} { printf "%s", if game[i, j] then if t=i then j else i else ""; printf "%s", if game[i, j] then " " else ""; } printf "\n"; } printf "*** pairings ***\n"; printf "{"; for {r in rounds} { for {i in teams, j in teams: i < j} { printf "%s", if roundGame[r, i, j] then "{" else ""; printf "%s", if roundGame[r, i, j] then i else ""; printf "%s", if roundGame[r, i, j] then "," else ""; printf "%s", if roundGame[r, i, j] then j else ""; printf "%s", if roundGame[r, i, j] then "}," else ""; } } printf "}\n"; printf "*** pairings with no games in common ***\n"; for {i in teams, j in teams: i < j} { printf "%s", if not incommon[i, j] then "{" else ""; printf "%s", if not incommon[i, j] then i else ""; printf "%s", if not incommon[i, j] then "," else ""; printf "%s", if not incommon[i, j] then j else ""; printf "%s", if not incommon[i, j] then "}," else ""; } data; end; Here's the output: INTEGER OPTIMAL SOLUTION FOUND Time used: 278.0 secs Memory used: 17.0 Mb (17850779 bytes) *** rounds *** Round 1: 1v8 2v9 3v10 4v11 5v12 6v13 7v14 Round 2: 1v6 2v14 3v5 4v13 7v11 8v12 9v10 Round 3: 1v4 2v3 5v7 6v9 8v10 11v12 13v14 Round 4: 1v2 3v4 5v6 7v8 9v11 10v13 12v14 *** opponents *** Team 1: 2 4 6 8 Team 2: 1 3 9 14 Team 3: 2 4 5 10 Team 4: 1 3 11 13 Team 5: 3 6 7 12 Team 6: 1 5 9 13 Team 7: 5 8 11 14 Team 8: 1 7 10 12 Team 9: 2 6 10 11 Team 10: 3 8 9 13 Team 11: 4 7 9 12 Team 12: 5 8 11 14 Team 13: 4 6 10 14 Team 14: 2 7 12 13 *** pairings *** {{1,8},{2,9},{3,10},{4,11},{5,12},{6,13},{7,14},{1,6},{2,14},{3,5},{4,13},{7,11},{8,12},{9,10},{1,4},{2,3},{5,7},{6,9},{8,10},{11,12},{13,14},{1,2},{3,4},{5,6},{7,8},{9,11},{10,13},{12,14}} *** pairings with no games in common *** Interestingly, although the round 1 games are needed, it doesn't seem to make much difference to the resolution time whether the round 2 condition is supplied or not - it was only 5 seconds quicker. In the above model, the fixRound2 condition is commented out. Another interesting thing is that, using EXACTLY the same parameters, the compilation of glpsol 4.9 I downloaded from http://winglpk.sourceforge.net/ is unable to get the gap below 4.6% (the optimum is 0%), whereas it seems to solve fairly easily in the GUSEK 0.2 Windows IDE. This is exactly the opposite to another problem I have also been working on, in which I used GUSEK for development only because it took around 5x longer to resolve in that program. > 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." Have more than one Hotmail account? Link them together to easily access both. |
[Prev in Thread] | Current Thread | [Next in Thread] |