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

[Roberto Bagnara]

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