Hi, I would just try it out, should be just ten or so lines of code... For r=3 things might go well...
The basic pruning used for linear is that the min and max of each variable is adjusted to feasible values (feasible as reals and then rounded to integers). 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: Neill Clift [mailto:neillcl...@live.com] Sent: Wednesday, January 4, 2017 22:40 To: cschu...@kth.se; users@gecode.org Subject: Re: [gecode-users] Linear Diophantine Equations 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
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
