-------- Forwarded Message -------- From: Brendan McKay <[email protected]> To: Andrew Makhorin <[email protected]> Cc: [email protected] Subject: Re: [Help-glpk] [Fwd: Using glp_exact() after glp_simplex() has timed out] Date: Wed, 7 Jun 2017 23:20:48 +1000
Thanks. So far I have been successful with calling glp_adv_basis if glp_simplex times out. After that, glp_exact has so far (in many thousands of cases) always succeeded. The reason I want glp_exact is that I am proving mathematical theorems and can't rely on correct rounding of approximate numbers. In particular, if the floating-point solution is very close to an integer I need to know for sure whether it is below, equal or above the integer. All the input coefficients are integers. Thanks for this impressive software. Brendan. On 7/6/17 10:23 pm, Andrew Makhorin wrote: >> Hi, I use the exact solver for my work in combinatorics and find it >> very efficient for my problems (tens to hundreds of thousands of >> variables but only a few dozen constraints). >> >> GLPK 4.61 running on Ubuntu 14.04.5 LTS. >> >> As recommended in the manual, I call glp_simplex() first and then call >> glp_exact(), which usually gives a nice speedup. It set an iteration >> limit for glp_simplex() because sometimes it cycles. However, if the >> call to glp_simplex() returns due the number of iterations being exceeded >> (return GLP_EITLIM), sometimes glp_exact() then runs forever. > This happens in glp_exact due to the same reason as in glp_simplex--your > lp instance is most likely primal degenerate, and, unfortunately, > glp_exact has no feature (e.g. like Bland's rule) to prevent cycling. > > You may try to use a non-official pre-release of glpk 4.62, where > glp_simplex was provided with a feature to improve numerical stability > and prevent cycling; please see > http://lists.gnu.org/archive/html/help-glpk/2017-05/msg00030.html . > >> I get a >> never-ending sequence of outputs like this: >> >> 26194: infsum = 144 (33) >> 26406: infsum = 144 (33) >> 26619: infsum = 144 (33) >> 26831: infsum = 144 (33) >> 27044: infsum = 144 (33) >> 27257: infsum = 144 (33) >> 27469: infsum = 144 (33) >> >> I infer that glp_simplex() is leaving things in a state unsuitable for >> starting glp_exact(). In such a case it would be enough to force >> glp_exact() to begin with a blank slate rather than using the >> left-overs from a timed-out glp_simplex(). But how can I achieve >> that short of reconstructing the problem or keeping a copy? >> > You may call glp_std_basis or glp_adv_basis or write your own routine > to construct an initial lp basis; see Section 2.7 of the glpk reference > manual. This, however, may not help due to primal degeneracy. > > BTW, why do you need to call glp_exact? Doesn't glp_simplex provide > enough accuracy of the solution? > > > Andrew Makhorin > _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
