[gecode-users] Linear Diophantine Equations

[Christian Schulte]

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, cschulte at kth.se
Expert Researcher, SICS, cschulte at sics.se
-----Original Message-----
From: Neill Clift [mailto:neillclift at live.com] 
Sent: Wednesday, January 4, 2017 22:40
To: cschulte at kth.se; users at 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, 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: 4599 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20170105/ff8eb756/attachment.bin>