[gecode-users] Linear Diophantine Equations

[Neill Clift]

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.