[Bug-glpk] GLPK cannot solve this

[Tony Huerlimann]

Dear Glpk-developers,


A year ago I downloaded glpk4.0 and tried to solve the attached 
MPS-File, that could not be solved by glpk4.0.

Glpk said that PROBLEN HAS NO FEASIBLE SOLUTION, while various other 
solvers give me an identical optimal solution at 3133905.5062.

---------------------------
Your comment on this problem was:
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.
--------------------------

Now, I downloaded glpk4.4 and have still the same problem. glpk4.4 
cannot solve this problem.

I attached the corresponding zipped MPS-file: essa.mps (minimizing).

Best regrads
Tony Huerlimann
--

--------------------------------------------------
Dr. PD Tony Huerlimann
Departement of Informatics, University of Fribourg
Site Regina Mundi, rue Faucigny 2
CH-1700 Fribourg / Switzerland

email: address@hidden
 or  : address@hidden
www  : www.virtual-optima.com
phone: +41 26  300 83 45
fax  : +41 26  300 97 26
---------------------------------------------------

ESSA.zip
Description: Mac BinHex archive