[ Post a Response | Puzzles Forum ]
Posted by Moby Dick
on 11/8/2009, 9:08 am, in reply to "15+ status"
> I've found a number of solutions for 15 without the time slot constraint, but none with it.
I would be surprised if it were possible to create the list of games, but not be able to form them into rounds. I have written a function that forms a list of games into a linear programming model that then organises them into rounds. Would you mind posting a couple of lists of games for me to try, please?
Here's the Maxima function:
makerounds(games, numRounds) := (
print(cardinality(games), "games"),
print("// Objective function"),
print("min: ;"),
print(" "),
print("// each game in 1 round only"),
for g in games do (
out: " = 1;",
for i: 1 thru numRounds do
out: sconcat(" + r", i, "_", part(g, 1), "_", part(g, 2), out),
print(out)
),
print(" "),
print("// same number of games in each round"),
for i: 1 thru numRounds do (
out: sconcat(" = ", floor(cardinality(games) / numRounds), ";"),
for g in games do
out: sconcat(" + r", i, "_", part(g, 1), "_", part(g, 2), out),
print(out)
),
print(" "),
print("// each team plays once in each round"),
numTeams: 0,
for g in games do
for team in g do
if (team > numTeams) then
numTeams: team,
for i: 1 thru numRounds do
for team: 1 thru numTeams do (
out: " = 1;",
for g in games do
if (elementp(team, g)) then
out: sconcat(" + r", i, "_", part(g, 1), "_", part(g, 2), out),
print(out)
),
print(" "),
print("// binary variables"),
out: "bin",
for g in games do
for i: 1 thru numRounds do
out: sconcat(out, " r", i, "_", part(g, 1), "_", part(g, 2)),
print(sconcat(out, ";"))
);
Here's an example:
makerounds({{1,2}, {1,3}, {2, 4}, {3,4}}, 2)$
4 games
// Objective function
min: ;
// each game in 1 round only
+ r2_1_2 + r1_1_2 = 1;
+ r2_1_3 + r1_1_3 = 1;
+ r2_2_4 + r1_2_4 = 1;
+ r2_3_4 + r1_3_4 = 1;
// same number of games in each round
+ r1_3_4 + r1_2_4 + r1_1_3 + r1_1_2 = 2;
+ r2_3_4 + r2_2_4 + r2_1_3 + r2_1_2 = 2;
// each team plays once in each round
+ r1_1_3 + r1_1_2 = 1;
+ r1_2_4 + r1_1_2 = 1;
+ r1_3_4 + r1_1_3 = 1;
+ r1_3_4 + r1_2_4 = 1;
+ r2_1_3 + r2_1_2 = 1;
+ r2_2_4 + r2_1_2 = 1;
+ r2_3_4 + r2_1_3 = 1;
+ r2_3_4 + r2_2_4 = 1;
// binary variables
bin r1_1_2 r2_1_2 r1_1_3 r2_1_3 r1_2_4 r2_2_4 r1_3_4 r2_3_4;
I have also tested it with a solution to 12 teams and 4 rounds - and it worked fine.
I have also written a program to produce an LP model for the entire problem: it works fine with 12 teams and 4 rounds, producing a solution in around 2 seconds - but unfortunately 14 teams and 4 rounds seems to be beyond the ability of LP_Solve to resolve even overnight - leaving me to think that the best way to resolve this problem would be a recursive function in a fast language with both each vertex (team) and each edge (game) being carefully checked for validity as it is added. Anyway - here's my function which won't solve this particular problem with LP_Solve, but probably would with a proprietary linear programming solver:
writeln(outputline) := printf(file, sconcat(outputline, ascii(13), ascii(10)));
(numTeams: 4,
numRounds: 2,
file: openw("c:/users/graham/documents/maths/lp_solve/tournament.lp"),
games: powerset(setify(makelist(i, i, 1, numTeams)), 2),
writeln("// Objective function"),
writeln("min: ;"),
writeln(" "),
writeln("// same number of games in each round"),
for i: 1 thru numRounds do (
out: sconcat(" = ", floor(numTeams / 2), ";"),
for g in games do
out: sconcat(" + r", i, "_", part(g, 1), "_", part(g, 2), out),
writeln(out)
),
writeln(" "),
writeln("// relate rounds to games"),
for g in games do (
out: "",
for i: 1 thru numRounds do
out: sconcat(" + r", i, "_", part(g, 1), "_", part(g, 2), out),
writeln(sconcat(out, " = g", part(g, 1), "_", part(g, 2), ";"))
),
writeln(" "),
writeln("// each team plays once in each round"),
for i: 1 thru numRounds do
for team: 1 thru numTeams do (
out: " <= 1;",
for g in games do
if (elementp(team, g)) then
out: sconcat(" + r", i, "_", part(g, 1), "_", part(g, 2), out),
writeln(out)
),
writeln(" "),
writeln("// edges per vertex (number of games each team will play)"),
for i: 1 thru numTeams do (
out: "",
for g in games do
if (elementp(i, g)) then
out: sconcat(out, " + g", part(g, 1), "_", part(g, 2)),
writeln(sconcat(out, " <= ", numRounds, ";"))
),
bin: "bin",
gamepairs: powerset(games, 2),
binset: {},
for g in games do (
writeln(" "),
writeln(sconcat("// do teams ", part(g, 1), " and ", part(g, 2), " have an opponent in common?")),
out: sconcat("// g", part(g, 1), "_", part(g, 2)),
for gp in gamepairs do (
i1: cardinality(intersection(set(part(g, 1)), part(gp, 1))) + cardinality(intersection(set(part(g, 1)), part(gp, 2))),
i2: cardinality(intersection(set(part(g, 2)), part(gp, 1))) + cardinality(intersection(set(part(g, 2)), part(gp, 2))),
if ((set(i1, i2) = {1, 1}) and (cardinality(union(part(gp, 1), part(gp, 2))) = 3)) then (
g1: sconcat(part(part(gp, 1), 1), "_", part(part(gp, 1), 2)),
g2: sconcat(part(part(gp, 2), 1), "_", part(part(gp, 2), 2)),
andvar: sconcat("g", g1, "&", g2),
binset: adjoin(andvar, binset),
out: sconcat(out, " or (g", g1, " and g", g2, ")")
)
),
writeln(out),
pairLim: sconcat("g", part(g, 1), "_", part(g, 2)),
for gp in gamepairs do (
i1: cardinality(intersection(set(part(g, 1)), part(gp, 1))) + cardinality(intersection(set(part(g, 1)), part(gp, 2))),
i2: cardinality(intersection(set(part(g, 2)), part(gp, 1))) + cardinality(intersection(set(part(g, 2)), part(gp, 2))),
if ((set(i1, i2) = {1, 1}) and (cardinality(union(part(gp, 1), part(gp, 2))) = 3)) then (
g1: sconcat(part(part(gp, 1), 1), "_", part(part(gp, 1), 2)),
g2: sconcat(part(part(gp, 2), 1), "_", part(part(gp, 2), 2)),
andvar: sconcat("g", g1, "&", g2),
pairLim: sconcat(pairLim, " + ", andvar),
writeln(sconcat(andvar, " <= g", g1, ";")),
writeln(sconcat(andvar, " <= g", g2, ";"))
)
),
writeln(sconcat(pairLim, " >= 1;"))
),
writeln(" "),
writeln("// binary variables"),
for g in games do
bin: sconcat(bin, " g", part(g, 1), "_", part(g, 2)),
for gp in binset do
bin: sconcat(bin, " ", gp),
for g in games do
for i: 1 thru numRounds do
bin: sconcat(bin, " r", i, "_", part(g, 1), "_", part(g, 2)),
writeln(sconcat(bin, ";")),
close(file)
)$
Sample output (4 teams, 2 rounds, instantaneous solution):
// Objective function
min: ;
// same number of games in each round
+ r1_3_4 + r1_2_4 + r1_2_3 + r1_1_4 + r1_1_3 + r1_1_2 = 2;
+ r2_3_4 + r2_2_4 + r2_2_3 + r2_1_4 + r2_1_3 + r2_1_2 = 2;
// relate rounds to games
+ r2_1_2 + r1_1_2 = g1_2;
+ r2_1_3 + r1_1_3 = g1_3;
+ r2_1_4 + r1_1_4 = g1_4;
+ r2_2_3 + r1_2_3 = g2_3;
+ r2_2_4 + r1_2_4 = g2_4;
+ r2_3_4 + r1_3_4 = g3_4;
// each team plays once in each round
+ r1_1_4 + r1_1_3 + r1_1_2 <= 1;
+ r1_2_4 + r1_2_3 + r1_1_2 <= 1;
+ r1_3_4 + r1_2_3 + r1_1_3 <= 1;
+ r1_3_4 + r1_2_4 + r1_1_4 <= 1;
+ r2_1_4 + r2_1_3 + r2_1_2 <= 1;
+ r2_2_4 + r2_2_3 + r2_1_2 <= 1;
+ r2_3_4 + r2_2_3 + r2_1_3 <= 1;
+ r2_3_4 + r2_2_4 + r2_1_4 <= 1;
// edges per vertex (number of games each team will play)
+ g1_2 + g1_3 + g1_4 <= 2;
+ g1_2 + g2_3 + g2_4 <= 2;
+ g1_3 + g2_3 + g3_4 <= 2;
+ g1_4 + g2_4 + g3_4 <= 2;
// do teams 1 and 2 have an opponent in common?
// g1_2 or (g1_3 and g2_3) or (g1_4 and g2_4)
g1_3&2_3 <= g1_3;
g1_3&2_3 <= g2_3;
g1_4&2_4 <= g1_4;
g1_4&2_4 <= g2_4;
g1_2 + g1_3&2_3 + g1_4&2_4 >= 1;
// do teams 1 and 3 have an opponent in common?
// g1_3 or (g1_2 and g2_3) or (g1_4 and g3_4)
g1_2&2_3 <= g1_2;
g1_2&2_3 <= g2_3;
g1_4&3_4 <= g1_4;
g1_4&3_4 <= g3_4;
g1_3 + g1_2&2_3 + g1_4&3_4 >= 1;
// do teams 1 and 4 have an opponent in common?
// g1_4 or (g1_2 and g2_4) or (g1_3 and g3_4)
g1_2&2_4 <= g1_2;
g1_2&2_4 <= g2_4;
g1_3&3_4 <= g1_3;
g1_3&3_4 <= g3_4;
g1_4 + g1_2&2_4 + g1_3&3_4 >= 1;
// do teams 2 and 3 have an opponent in common?
// g2_3 or (g1_2 and g1_3) or (g2_4 and g3_4)
g1_2&1_3 <= g1_2;
g1_2&1_3 <= g1_3;
g2_4&3_4 <= g2_4;
g2_4&3_4 <= g3_4;
g2_3 + g1_2&1_3 + g2_4&3_4 >= 1;
// do teams 2 and 4 have an opponent in common?
// g2_4 or (g1_2 and g1_4) or (g2_3 and g3_4)
g1_2&1_4 <= g1_2;
g1_2&1_4 <= g1_4;
g2_3&3_4 <= g2_3;
g2_3&3_4 <= g3_4;
g2_4 + g1_2&1_4 + g2_3&3_4 >= 1;
// do teams 3 and 4 have an opponent in common?
// g3_4 or (g1_3 and g1_4) or (g2_3 and g2_4)
g1_3&1_4 <= g1_3;
g1_3&1_4 <= g1_4;
g2_3&2_4 <= g2_3;
g2_3&2_4 <= g2_4;
g3_4 + g1_3&1_4 + g2_3&2_4 >= 1;
// binary variables
bin g1_2 g1_3 g1_4 g2_3 g2_4 g3_4 g1_2&1_3 g1_2&1_4 g1_2&2_3 g1_2&2_4 g1_3&1_4 g1_3&2_3 g1_3&3_4 g1_4&2_4 g1_4&3_4 g2_3&2_4 g2_3&3_4 g2_4&3_4 r1_1_2 r2_1_2 r1_1_3 r2_1_3 r1_1_4 r2_1_4 r1_2_3 r2_2_3 r1_2_4 r2_2_4 r1_3_4 r2_3_4;
Message Thread:
« Back to thread