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

[Sven Verdoolaege]

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