[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] glpk_intopt loops forever on a specific input when MIP pr
From: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] glpk_intopt loops forever on a specific input when MIP presolver enabled |
Date: |
Wed, 08 Nov 2017 07:17:30 +0300 |
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
- Re: [Bug-glpk] glpk_intopt loops forever on a specific input when MIP presolver enabled,
Andrew Makhorin <=