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

[Georgi Guninski]

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.

-- 
Georgi


On Sun, Dec 22, 2013 at 09:00:39AM +0100, Roberto Bagnara wrote:
> On 12/21/13 13:26, Georgi Guninski wrote:
> >I am trying to solve the following problem, not
> >necessarily with ppl.
> >
> >Given positive integers $A0,B0,L$ find integers $A,B$
> >satisfying:
> >
> >1 <= A
> >A <= L
> >1 <= B
> >B <= L
> >1 <= A0*A - B0*B
> >A0*A - B0*B <= L
> >
> >Encoded it in PPL by modifying an example (also attached):
> >=====
> >   Constraint_System cs;
> >   cs.insert(A  >= 1);
> >   cs.insert(A  <= Coefficient(L));
> >   cs.insert(B  >= 1);
> >   cs.insert(B  <= Coefficient(L));
> >   cs.insert(Coefficient(A0)*A - Coefficient(B0)*B >= 1);
> >   cs.insert(Coefficient(A0)*A - Coefficient(B0)*B <= Coefficient(L) );
> >
> >   // All integer variables.
> >   Variables_Set ivs(A, B);
> >
> >   // Cost function.
> >   Linear_Expression cost(Coefficient("10"));
> >
> >   MIP_Problem mip(cs.space_dimension(), cs.begin(), cs.end(), ivs, cost,
> >                   MINIMIZATION);
> >
> >   if (mip.solve() != OPTIMIZED_MIP_PROBLEM) {
> >
> >=======
> >(reads 3 ints from stdin)
> >
> >This works for small input, but for:
> >
> >A0=654013667618
> >B0=654013667619
> >L=808711
> >
> >PPL consumes 6GB RAM very fast and I run out of memory.
> >
> >Am I doing something wrong?
> >
> >Other ways to solve the problem?
> >
> >Attached is the source, function "test10".
> >
> >Thank you.
> >
> >ppl-1.1 on x86_64 linux.
> 
> Hello Georgi.  Thanks for the report.
> 
> As far as I can tell you are doing nothing wrong: simply, your
> constraint system (with A0 = 654013667618, B0 = 654013667619,
> and L = 808711) has no solution over the integers and the
> branch-and-bound implementation generates so many LP problems
> that it fills your memory.  Did you try with glpk or lp-solve?
> Kind regards,
> 
>    Roberto
> 
> P.S. Here is how I concluded there is no solution:
> 
> $ swipl
> Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.1.2)
> Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
> SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
> and you are welcome to redistribute it under certain conditions.
> Please visit http://www.swi-prolog.org for details.
> 
> For help, use ?- help(Topic). or ?- apropos(Word).
> 
> ?- use_module(library(clpfd)).
> %    library(pairs) compiled into pairs 0.00 sec, 22 clauses
> %   library(lists) compiled into lists 0.01 sec, 122 clauses
> %   library(occurs) compiled into occurs 0.00 sec, 14 clauses
> %  library(apply_macros) compiled into apply_macros 0.01 sec, 168 clauses
> %  library(assoc) compiled into assoc 0.00 sec, 103 clauses
> % library(clpfd) compiled into clpfd 0.11 sec, 2,769 clauses
> true.
> 
> ?- A0=654013667618, B0=654013667619, L=808711, 1 #=< A, A #=< L, 1 #=< B, 1 #=< A0*A - B0*B, A0*A - B0*B #=< L.
> false.
> 
> ?-
> 
> -- 
>      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
> _______________________________________________
> PPL-devel mailing list
> PPL-devel at cs.unipr.it
> http://www.cs.unipr.it/mailman/listinfo/ppl-devel