[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] [Fwd: Using glp_exact() after glp_simplex() has timed ou
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] [Fwd: Using glp_exact() after glp_simplex() has timed out] |
Date: |
Wed, 07 Jun 2017 15:23:51 +0300 |
> 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