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

[Tawny Owl]

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.