> I have a problem that has few integer parameters defining the size > of the problem. It's like the large non-square underdefined linear > equation AX=F with extra >= conditions.
> When I downscale parameters such that problem becomes just the > square linear equation GLPK fails with error beginning with size > ~700: > 0: objval = 1.427134885e-02 infeas = 1.000000000e+00 (0) > 200: objval = 3.448379584e-03 infeas = 3.724860891e-01 (0) > 203: objval = -7.866243389e-19 infeas = 1.314442221e-16 (500) > * 203: objval = -7.866243389e-19 infeas = 8.259452150e-16 (500) > * 400: objval = 0.000000000e+00 infeas = 0.000000000e+00 (303) > spx_invert: the basis matrix is ill-conditioned > spx_simplex: numerical problems with basis matrix > spx_simplex: sorry, basis recovery procedure not implemented yet > lpx_simplex: cannot recover undefined or non-optimal solution > Time used: 26.0 secs > Memory used: 104.3M This a lack of the glpk simplex solver. I hope to implement a new version of the solver, which includes the basis recovery procedure. > This suggests that GLPK failed to compute LU-factorization of the A > matrix. At the same time LAPACK package is able to find > LU-factorization and invert the same matrix quite easily with their > 'dgetrf' and 'dgetri' functions called in sequence. > Is it reasonable to expect GLPK to invert this kind of matrices? > Would this be a valid enhancement request? Ill-conditioned matrix means that its condition number is too large (in this case is larger than 1e12), so the solution cannot be obtained with a sufficient accuracy. AFAIK, dgetrf checks only for exact singularity, besides it uses partial pivoting. Could you estimate the condition number of your matrix? > I can provide this problem's description if necessary. Please do that. Andrew Makhorin _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
