[Bug-glpk] GLPSOL outputs MIP solution that is not LP optimal for fixed integers

[xypron]

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.