
From:  Tawny Owl 
Subject:  [Helpglpk] Time Limit Didn't Work On Tournament Model 
Date:  Sat, 5 Sep 2009 11:46:57 +0100 
Hi GLPK help list, I ran a model (appended below) with a time limit of a little over 8 hours  but it didn't stop at 8 hours. I used the following parameters: cover clique gomory mir fpump tmlim 30000 m "tournament.mod" After around 5 hours, the output was as follows: Time used: 20408.7 secs. Memory used: 111.2 Mb. +4458716: mip = 8.900000000e+001 <= 9.100000000e+001 2.2% (1896; 29892) +4458835: mip = 8.900000000e+001 <= 9.100000000e+001 2.2% (1897; 29892) +4459129: mip = 8.900000000e+001 <= 9.100000000e+001 2.2% (1897; 29893) +4460056: mip = 8.900000000e+001 <= 9.100000000e+001 2.2% (1897; 29893) +4461852: mip = 8.900000000e+001 <= 9.100000000e+001 2.2% (1897; 29893) +4462019: mip = 8.900000000e+001 <= 9.100000000e+001 2.2% (1898; 29893) +4462885: mip = 8.900000000e+001 <= 9.100000000e+001 2.2% (1899; 29893) 4468000: obj = 9.100000000e+001 infeas = 0.000e+000 (3) 4468200: obj = 9.100000000e+001 infeas = 0.000e+000 (3) 4468400: obj = 9.100000000e+001 infeas = 0.000e+000 (3) 4468600: obj = 9.100000000e+001 infeas = 0.000e+000 (3) 4468800: obj = 9.100000000e+001 infeas = 0.000e+000 (3) 4469000: obj = 9.100000000e+001 infeas = 0.000e+000 (3) ...this continued well beyond the time limit, and in the end, I had to stop it without getting the solution... 12474200: obj = 9.100000000e+001 infeas = 0.000e+000 (3) 12474400: obj = 9.100000000e+001 infeas = 0.000e+000 (3) 12474600: obj = 9.100000000e+001 infeas = 0.000e+000 (3) >Process failed to respond; forcing abrupt termination... >Exit code: 1 Time: 39874.696 What has gone wrong, please? 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. It will be clear what this model is doing if you run it with teams set to 1..4 and rounds set to 1..2, when it will resolve immediately. Model: # make fixture list to minimise cases of pairs of teams in a tournament 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} binary; 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)} binary; var incommon {i in teams, j in teams: i < j} binary; maximize gamesInCommon: sum{i in teams, j in teams: i < j} incommon[i, j]; # identify game pairs s.t. identifyGamePairs{i in teams, j in teams, k in teams: i < j and not (i = k or j = k)}: gamepair[i, j, k] <= (0.5 * game[min(i, k), max(i, k)]) + (0.5 * 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; Use Hotmail to send and receive mail from your different email accounts. Find out how. 
[Prev in Thread]  Current Thread  [Next in Thread] 