Hello Andrew, I have solved the model below with glpsol.exe --fpump -m test.mod --tmlim 30
(derived from http://lists.gnu.org/archive/html/help-glpk/2009-09/msg00015.html http://lists.gnu.org/archive/html/help-glpk/2009-09/msg00015.html ) The output was + 1763: mip = 1.041490000e+002 <= 1.200000000e+002 15.2% (2; 0) TIME LIMIT EXCEEDED; SEARCH TERMINATED ... incommon[2,3] = 0.148999999999954 ... gamepair[2,3,4] = 1 sum{}incommon is to be maximized. The only contraint limiting requires incommon[i, j] <= sum{r in rounds}roundGame[r,i,j] + sum{k in teams: i != k and j != k} gamepair[i, j, k]; roundGame is binary. Hence I would have expected a solution with incommon[2,3] = 1 if gamepair[2,3,4] = 1. I would not have expected a MIP solution to yield an noninteger objective for this model. This strange behaviour only occurs if the feasibility pump is used. Could it be that it adds some cut that is not part of the original problem? Best regards Xypron # 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..16; set rounds:= 1..4; 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]; # first round s.t. r1{ j in teams : j mod 2 = 0 } : roundGame[1,j-1,j] = 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] <= sum{r in rounds}roundGame[r,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] <= sum{r in rounds}roundGame[r,min(j, k), max(j, k)]; # identify opponents in common s.t. opponentsInCommon{i in teams, j in teams: i < j}: incommon[i, j] <= sum{r in rounds}roundGame[r,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] <= 1; # 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 sum{r in rounds} roundGame[r,i, j] then if t=i then j else i else ""; printf "%s", if sum{r in rounds} roundGame[r,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 ""; } display incommon; display gamepair; data; end; -- View this message in context: http://www.nabble.com/GLPSOL-outputs-MIP-solution-that-is-not-LP-optimal-for-fixed-integers-tp25337983p25337983.html Sent from the Gnu - GLPK - Bugs mailing list archive at Nabble.com. _______________________________________________ Bug-glpk mailing list Bug-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/bug-glpk