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

[Tawny Owl]

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.