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

[Andrew Makhorin]

-------- Forwarded Message --------
From: Brendan McKay <address@hidden>
To: Andrew Makhorin <address@hidden>
Cc: address@hidden
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
>