Re: [Bug-glpk] glpk_intopt loops forever on a specific input when MIP presolver enabled

[Andrew Makhorin]

Thank you for your bug report.

> I'm using the latest version of your library (4.63) and I came across
> a specific LP problem instance, that causes looping forever when
> the MIP presolver is enabled. 

> I'm sending you the problem definition in the attachment (problem.lp
> file). You should be able to replicate the behavior by executing the
> CLI of your library. I include the commands I tried:

> My first approach:

> "glpsol --lp problem.lp"     -> loops forever with the warning
> "Warning: numerical instability (primal simplex, phase II)"
> 
> So I assumed that maybe it is due to poor scaling, so I tried:

> "glpsol --lp --scale problem.lp"    -> loops forever the same way

--scale option is enabled by default.

> So I tried disabling the presolver, but still no luck:

> "glpsol --lp --scale --nopresol problem.lp"    -> loops forever the
> same way

--nopresol option affects only lp, not mip.

> So I tried disabling the MIP presolver and finally, I got the result:

> "glpsol --lp --scale --nopresol --nointopt problem.lp"     -> finally
> gave a result

> Also "glpsol --lp --nointopt problem.lp" works which points to the MIP
> presolver as the "faulty" part.

Yes, glpsol fails on your instance because of the mip preprocessor.

> Could you explain me why the involvement of the MIP presolver causes
> such behavior? Is it a bug 

No, I don't think so. Most probably the mip preprocessor introduces
excessive round-off errors. I need a time to perform more detailed
analysis. Interesting to note that if glpk is compiled with the gcc
option -O0, glpsol solves your mip successfully, and the instability
doesn't appear.

> or is my LP problem instance just poorly defined? If it is poorly
> defined, how to correct the problem definition by the operations
> available in your library (like scaling, presolving, ...) without
> losing precision?
> 

I wouldn't say that your mip is badly formulated. However, you may try
to reformulate it to reduce the ranges of integer variables x_1 and x_6.
In particular, try to remove integrality constraints for these variables
and see what happens.


Andrew Makhorin