[Bug-glpk] Re: feasible LP declared infeasible by GLPK

[Andrew Makhorin]

Thank you for your bug report.

>I have a MPS file containing a MIP. It solves fine using either of the two 
>NEOS solvers
>available on the web: FORTMP and Xpress-MP in less than a tenth of a second.
>When I try to solve it using GLPK, it tells me that it has no feasible 
>solution. This is
>while trying to solve the LP relaxation using simplex.

I tried solving your problem with glpsol with default settings and there
were no errors:

------------------------------------------------------------------------
load_mps: reading LP data from `bigun-out.mps'...
load_mps: name `Unnamed'
load_mps: 223 rows
load_mps: 428 columns
load_mps: 1384 non-zeros
load_mps: 1 right-hand side vector(s)
load_mps: 0 range vector(s)
load_mps: 1 bound vector(s)
load_mps: 1180 cards were read
lpx_simplex: original LP has 223 rows, 428 columns, 1384 non-zeros
lpx_simplex: presolved LP has 222 rows, 227 columns, 1067 non-zeros
gm_scal: max / min = 1.000e+05
gm_scal: max / min = 1.207e+00
lpx_adv_basis: size of triangular part = 222
      0:   objval =   7.345651743e+05   infeas =   1.000000000e+00 (0)
     17:   objval =   2.000000000e+05   infeas =  -1.099245478e-16 (0)
*    18:   objval =   2.000000000e+05   infeas =   3.335109966e-13 (0)
*    47:   objval =  -3.517512642e-12   infeas =   1.421085472e-13 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+    47: mip =     not found yet; lp =   0.000000000e+00 (1, 0)
+    47: mip =   0.000000000e+00; lp =   0.000000000e+00 (1, 0)
+    47: mip =   0.000000000e+00; lp =     tree is empty (0, 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.6M (599876 bytes)
------------------------------------------------------------------------

However changing some settings I found that when I was specifying the
options --nopresol (do not use the presolver) and --std (use the standard
initial basis), glpsol reported that the problem has no feasible solution,
i.e. as in your case.

This error happens due to a routine that checks reduced costs for the sum
of infeasibilities on the phase I of the simplex method. For your problem
(due to large right-hand sides, as it seems to me) the routine finds that
the sum is still positive and cannot be decreased, so it reports that the
problem has no primal feasible solutions. In other word, this is a defect
of the implementation. (I've got some small lp problems which cause the
same error not only for glpk, but also for such well known lp solvers as
cplex, xpress, and minlp. Unfortunately, the floating point arithmetic is
inexact.)

To avoid the error try to call the api routine lpx_adv_basis before
the first call to the routine lpx_simplex in order to use an advanced
initial basis. (Please report to me if this helps or not).

>The MPS file is attached.
>For future reference, should I be posting such reports to this list?

Yes. This list is just for such reports.


Andrew Makhorin