[PPL-devel] Out of memory when solving integer problem with only two large vars

[Georgi Guninski]

On Mon, Dec 23, 2013 at 09:16:40AM +0100, Sven Verdoolaege wrote:
> On Sun, Dec 22, 2013 at 02:06:06PM +0200, Georgi Guninski wrote:
> > Many thanks for the prolog solution!
> > 
> > If I remove the last constraint (comment it in the code):
> > 
> > //cs.insert(Coefficient(A0)*A - Coefficient(B0)*B <= Coefficient(L) );//XXX
> > 
> > Then try with:
> > A0=654013667618
> > B0=654013667619
> > L= 654013667617
> > 
> > I again run out of memory, why so?
> > (swipl finds solutions even to the original problem for these values).
> > 
> > Last time I checked glpk and lp-solve they don't support
> > large integers - work modulo 2^32 or 2^64 and don't
> > give correct solutions over the integers
> > 
> > PPL is the only free solver I know of supporting
> > large integers.
> 
> Didn't you just say that SWI-Prolog works for you?
> 
> In any case, there is also isl:
> 
>     $ ./isl_polyhedron_sample 
>     { [A,B] : 1 <= A and A <= 808711 and 1 <= B and 1 <= 654013667618 * A - 654013667619 * B <= 808711 }
>     []
>     $ ./isl_polyhedron_sample 
>     { [A,B] : 1 <= A and A <= 808711 and 1 <= B and 1 <= 654013667618 * A - 654013667619 * B <= 654013667617 }
>     [1,404356,404355]
>     $ ./isl_polyhedron_sample 
>     { [A,B] : 1 <= A and A <= 808711 and 1 <= B and 1 <= 654013667618 * A - 654013667619 * B }
>     [1,808711,1]
> 
> (The first "1" in the output is the denominator and is always "1",
> if there is a solution.)
> 
> skimo


Thank you for the isl solution Sven!

isl solves in seconds a minor modification for L ~ 2^70 while
swi-prolog couldn't solve it in 3 hours.

Good luck with PPL development.