Re: [Help-glpk] Does it mean no optimal solution is found??

[Andrew Makhorin]

> I create an LP problem by specifying an objective function and some
> constraints. Some of my parameter sets yield optimal solutions for this
> LP problem, however in some cases I got the following output, which
> cannot find any optimal solution after the last parameter becomes (0),
> and after that point it loops infinitely by giving the "spx_prim_chuzc:
> recomputing basic solution components" debug output.
> 
> Does this mean there is no optimal solution for this LP problem, or may
> it be some kind of a bug that I can correct it?? By the way I am just
> using glpk to solve my problem, so I am not an LP theory expert. Please
> excuse me for the incovenience.
>  
> 
> Solving using Simplex Method...
> lpx_adv_basis: size of triangular part = 2296
> *     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (1)
> *   200:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (1)
> *   400:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (1)
> *   600:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (1)
> *   800:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (1)
> *  1000:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (1)
> *  1200:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (1)
> *  1400:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (1)
> *  1600:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
> *  1800:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
> *  2000:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
> *  2200:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
> spx_prim_chuzc: recomputing basic solution components
> spx_prim_chuzc: recomputing basic solution components
> *  2400:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
> spx_prim_chuzc: recomputing basic solution components
> spx_prim_chuzc: recomputing basic solution components
> spx_prim_chuzc: recomputing basic solution components
> spx_prim_chuzc: recomputing basic solution components

Unfortunately, this is a defect of the glpk simplex solver. Due to
round-off errors the current basic solution is found inaccurate, and
the solver tries recomputing its components to improve it, however,
the try fails, probably, because the problem is badly scaled, that,
in turns, prevents from normal termination of the search.

If you wish, you can post me your instance in a format supported by
glpsol for further analysis.

Andrew Makhorin