[Help-glpk] Re: GLPK & Lazy Theorem Proving

[Andrew Makhorin]

Hi Christian,

Thank you for your interest in glpk.

> Now to my questions:
> 
> 
> 1) Because of the allocation and deallocation operations entailed,
> it seemed to me rather inefficient to actually add (retract) a
> linear constraint to (from) the LP each time the corresponding guard
> variable changes its truth value.
> 
> Instead I opted for
> 
> * initially (before solving starts) setting up a linear program
>    containing *all* constraints from M, the latter however being
>    'switched off' by setting their relops to LPX_FR,
> 
> * 'activating' a constraint whose guard variable is assigned to true
>    by setting its relop to LPX_UP, LXP_LO, or LPX_FX, respectively, and
> 
> * deactivating a constraint whose guard variable is unassigned by
>    resetting its relop to LPX_FR.
> 
> My first questions is if my assumption is correct that linear constraints
> which are switched off in the way described above are ignored by
> GLPK in the sense
> 
> a) that they do not affect the correctness of the solving process, and
> 
> b) that they don't add much computational overhead to solving (compared
>     to the scenario where they are actually removed from the LP matrix.)

Yes, your assumption is correct. This is normal way to activate/
deactivate some constraints. However, you also should not change the
current basis (in the sense of basic and non-basic variables) before
reoptimization in order to allow the simplex solver using the current
inverse of the basis matrix. Only in this case you can achieve the
maximum of efficiency.

> 
> 
> 2) Occasionally I've encountered the problem that GLPK stops with an
> assertion failure:
> 
 >> Assertion failed: spx->p != 0; file glpspx2.c; line 668
> 
>  From your posts on help-glpk I've learned that this behaviour can
> be caused by ill-conditioned LPs.
> In some cases, however, I made the following strange observation:
> If I write the bad-behaving LP to a file, thereafter re-read it and
> solve it (with exactly the same solver settings), then the assertion
> failure does not occur.

In the first case the simplex solver continues the search from the
current basis while in the second case the solver starts from an
initial basis (either trivial or constructed by the crashing
procedure). The error occurs because in the first case the search
encounters an intermediate point (vertex) having ill-conditioned
basis.

>
> The only explanation I can think of is that switching constraints
> on and off numerous times, each time followed by solving the resultant LP,
> somehow screws up GLPK's internal data-structures, so that it behaves
> different compared to a 'freshly created' GLPK instance.

Changes in the problem instance are not "accumulated". The error
appears due to the starting basis used on reoptimization.

> 
> Do you think this can happen? Do you have some hints how I could
> fix this problem (or how to proceed to further diagnose it)?
> Unfortunately, my insight into the internal working of GLPK is
> still very limited.

Try to replace the line 668 (file glpspx2.c):

         insist(spx->p != 0);

by the following fragment:

         if (spx->p == 0)
         {  ret = LPX_E_INSTAB;
            break;
         }

This, of course, is not an elegant solution, however, will allow the
solver at least to continue the search.


Best regards,

Andrew Makhorin