[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] [Fwd: Re: [Fwd: Using glp_exact() after glp_simplex() has ti
[Help-glpk] [Fwd: Re: [Fwd: Using glp_exact() after glp_simplex() has timed out]]
Wed, 07 Jun 2017 17:59:07 +0300
-------- Forwarded Message --------
From: Brendan McKay <address@hidden>
To: Andrew Makhorin <address@hidden>
Subject: Re: [Help-glpk] [Fwd: Using glp_exact() after glp_simplex() has
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.
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
|[Prev in Thread]
||[Next in Thread]|
- [Help-glpk] [Fwd: Re: [Fwd: Using glp_exact() after glp_simplex() has timed out]],
Andrew Makhorin <=