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;
_________________________________________________________________
Access your other email accounts and manage all your email from one place.
http://clk.atdmt.com/UKM/go/167688463/direct/01/_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
