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, 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 _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
