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

[Mritunjay Singh]

Thank you very much. It works if I call lpx_adv_basis before lpx_simplex. I 
wonder why
the default settings are not being used automatically. Perhaps it's a quirk of 
the java
interface (I should have mentioned, I'm using the Java interface). 
I'll look into raising the lower bound on some variables as you suggest.

Thanks again
-M

--- Andrew Makhorin <address@hidden> wrote:
> 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
> 


__________________________________
Do you Yahoo!?
SBC Yahoo! DSL - Now only $29.95 per month!
http://sbc.yahoo.com