Hi Neill, Gecode uses standard propagation techniques for linear equations: depending on the size and values of the a_i propagation tends to be rather weak. It can use domain consistent propagation for the linear constraint but its complexity is exponential.
It might work reasonably well for small r but why not using a linear integer
programming solver:
https://en.wikipedia.org/wiki/Integer_programming
Cheers
Christian
--
Christian Schulte, www.gecode.org/~schulte
Professor of Computer Science, KTH, cschu...@kth.se
Expert Researcher, SICS, cschu...@sics.se
-----Original Message-----
From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf
Of Neill Clift
Sent: Wednesday, January 4, 2017 01:00
To: users@gecode.org
Subject: [gecode-users] Linear Diophantine Equations
Hi,
I was wondering if people thought if constraint satisfaction in general and
more specifically gecode was suitable for solving quickly a system system
like this:
$a_1x_1+a_2x_2+...+a_rx_r=n$
$1 \leq a_i$
$1 \leq x_i \leq 2^l$
$1 \leq l$
All variables are integers. a_i is given. We want to find the x_i's.
I have billions of these problems that I could attempt to solve in an
algorithm I have for computing optimal addition chains. Currently I am only
solving cases with $r=2$ using extended gcd. This gives me a very powerful
prune in the code.
Do you think gecode solves these type of problems efficiently? I know I can
do the equivalent of extended gcd in higher dimensions with the Blankinship
algorithm etc and then try to enumerate solutions via the specific solution
and the null space but I haven't managed to achieve anything with this
approach yet.
What techniques does gecode use to solve such systems (assuming you have
something special for linear constraints)?
I have written code using gecode before so I am familiar with it's usage. I
am just trying to understand if it might be a good approach or if there are
good approaches from constraint satisfaction.
Thanks.
Neill.
_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
