Re: [Help-glpk] [Fwd: Using glp_exact() after glp_simplex() has timed out]

[Andrew Makhorin]

> 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