[gecode-users] Linear Diophantine Equations

[Christian Schulte]

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, cschulte at kth.se
Expert Researcher, SICS, cschulte at sics.se


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Neill Clift
Sent: Wednesday, January 4, 2017 01:00
To: users at 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 at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4623 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20170104/f8aa1ea7/attachment.bin>