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

[Roberto Bagnara]

On 12/23/13 11:25, Georgi Guninski wrote:
> 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.

Neither the PPL, nor SWI-Prolog, nor isl are the right tools for this
problem.  What you need is the extended Euclidean algorithm.
PPL contributor Alessandro Zaccagnini can tell you more about this.
Kind regards,

    Roberto

-- 
      Prof. Roberto Bagnara

Applied Formal Methods Laboratory - University of Parma, Italy
mailto:bagnara at cs.unipr.it
                               BUGSENG srl - http://bugseng.com
                               mailto:roberto.bagnara at bugseng.com