[Help-glpk] Re: MIP rounding

[Jean-Sebastien Roy]

On Mon, 07 Jul 2003 14:12:35 +0400
"Andrew Makhorin" <address@hidden> wrote:

> >Minimize
> >obj: c
> >Subject To
> >cst: x - 1000000.0 c <= 0
> >Bounds
> >0.5 <= x
> >Binaries
> >c
> >End
> >
> >Whose solution is c = 1, x = 0.5. (min = 1)
> >GLPK is quite happy to answer c = 0, x = 0.5. (min = 0 !)
> 
> This is a common difficulty that arises due to "big M". In fact, one

Thanks for your answer (and all the great work on GLPK).

I fully understand the problems associated with the big M (and the
painful amount of adjustments needed to get a suitable M). But still,
don't you think that performing some amount of checking at the end of
the optimisation, even if only to raise a warning, would be useful ?
CPLEX seems to be doing this kind of calculations (fixing the bound on
the integer variables to thier optimal values, and then trying to solve
the LP). At least it would help find problems in the LP ? GLPK does some
checking in the LP case (KKT conditions) but not in the MILP case.

As a side note, in the same vein, GLPK solves the following problem
using only it's presolver (feasible (!), c=0, x=0.5) :

Minimize
obj: c
Subject To
cst: 1.0e-5 x - 1.0 c <= 0
Bounds
0.5 <= x
0 <= c <= 0
End

It's only a precision setting, but no other solver I tested found it
feasible.

Regards,

js