[Bug-glpk] Re: None

[Andrew Makhorin]

Thank you for your report.

>However, recently I solved an LP. Glpk says that PROBLEN HAS NO 
>FEASIBLE SOLUTION, while various other solvers give me an identical 
>optimal solution at 3133905.5062.

Looks like the feasible region in your problem is very small and very
stretched in some directions. I was unable to solve the problem using
different settings in glpsol, however I've managed to solve it using
other simplex code for the phase I (which is currently not included
in glpk). Interesting to note that after a feasible solution was found,
only a few iterations were needed to reach the optimum, however the
objective was being changed significantly (from 1e10 to 3e6).

Actually the glpk simplex code for the phase I does find a feasible
solution, and the difficulty arises when the solver tries to drive
away an artificial variable from the basis, that is needed to start the
phase II. That variable is a measure of primal infeasibility and it is
close to zero, i.e. the current basis is primal feasible. However,
after the artificial variable has left the basis, the adjacent basis
becomes primal infeasible (that must not happen) due to excessive
round-off errors. Unfortunately, on restarting the phase I from the
current point (to find a feasible solution which would satisfy internal
tolerances), reduced costs for a new artificial objective become close to
zero, and the problem is treated as having no primal feasible solution.
I hope to correct the situation by revising some internal feasibility
tests.

Andrew Makhorin