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

[xypron]

Hello 

http://lists.gnu.org/archive/html/bug-glpk/2009-09/msg00002.html
http://lists.gnu.org/archive/html/bug-glpk/2009-09/msg00002.html 
describes that tmlim is only checked after the simplex algorithm has found a
solution
for the current node of the branch and bound algorithm.

Looking at your model it seems that the number of boolean variables could be
reduced
drastically, this might reduce the total runtime.

Game can be defined as float as it is the sum of binaries which can not
exceed 1.
var game {i in teams, j in teams: i < j};

Incommon can be defined as float without changing the solution
var incommon {i in teams, j in teams: i < j}, >=0, <=1;

Gamepair can be defined as float if the constraint identifyGamePairs is
changed:
var gamepair {i in teams, j in teams, k in teams: i < j
  and not (i = k or j = k)}, >=0, <=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)];

Best regards

Xypron


gandtandb-2 wrote:
> 
> 
> 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;
> ...
> 

-- 
View this message in context: 
http://www.nabble.com/Time-Limit-Didn%27t-Work-On-Tournament-Model-tp25307099p25335449.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.