bug-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Bug-glpk] GLPSOL outputs MIP solution that is not LP optimal for fi


From: Andrew Makhorin
Subject: Re: [Bug-glpk] GLPSOL outputs MIP solution that is not LP optimal for fixed integers
Date: Mon, 14 Sep 2009 03:54:16 +0400

Hi Xypron,

> 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.

'incommon' is declared as continuous:

var incommon {i in teams, j in teams: i < j}, >=0, <=1;

so I do not see a problem. Why do you think that all components of
'incommon' must be integral?

> 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?

Currently the fpump heuristic is applied prior to cut generation.






reply via email to

[Prev in Thread] Current Thread [Next in Thread]