> 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
