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

[Georgi Guninski]

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.

-- 
Georgi


-------------- next part --------------
A non-text attachment was scrubbed...
Name: mipproblem1.cc
Type: text/x-c++src
Size: 67532 bytes
Desc: not available
URL: <http://www.cs.unipr.it/pipermail/ppl-devel/attachments/20131221/3b2f2b90/attachment.cc>