[gecode-users] Linear Diophantine Equations

[Neill Clift]

Hi,
Thanks for your response. I was hoping there was some technique I wasn't 
aware of used in constraint satisfaction systems.
r is small in my system. In fact just having something for r=3 would be 
a big deal. It has to be very fast though as this would be a prune.
I am familiar with integer programming but I thought using something 
like glpk would be too slow.
Neill.

On 1/4/2017 3:03 AM, Christian Schulte wrote:
> 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