Out of memory when solving integer problem with only two large vars
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.
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.
?-
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.
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
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.
Good luck with PPL development.
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
participants (3)
-
Georgi Guninski -
Roberto Bagnara -
Sven Verdoolaege