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. -- Georgi
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@cs.unipr.it BUGSENG srl - http://bugseng.com mailto:roberto.bagnara@bugseng.com
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@cs.unipr.it BUGSENG srl - http://bugseng.com mailto:roberto.bagnara@bugseng.com _______________________________________________ PPL-devel mailing list PPL-devel@cs.unipr.it http://www.cs.unipr.it/mailman/listinfo/ppl-devel
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 -- Prof. Roberto Bagnara Applied Formal Methods Laboratory - University of Parma, Italy mailto:bagnara@cs.unipr.it BUGSENG srl - http://bugseng.com mailto:roberto.bagnara@bugseng.com
participants (3)
-
Georgi Guninski -
Roberto Bagnara -
Sven Verdoolaege