[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bug-glpk] Re: feasible LP declared infeasible by GLPK
From: |
Mritunjay Singh |
Subject: |
[Bug-glpk] Re: feasible LP declared infeasible by GLPK |
Date: |
Thu, 19 Jun 2003 15:50:12 -0700 (PDT) |
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