Re: Arthmetic constraints in eclipse

From: Warwick Harvey <wh_at_icparc.ic.ac.uk>
Date: Wed 15 Jan 2003 02:36:41 PM GMT
Message-ID: <20030115143640.C16824@tempest.icparc.ic.ac.uk>
On Tue, Jan 14, 2003 at 05:10:29PM +0000, Christopher Jefferson wrote:
> Hello!
> 
> I am performing a study into arithmetic constraints in CSPs and the best 
> ways of representing them, so would like to be sure I know what eclipse 
> currently does.
> 
> It appears to me that eclipse will multiply out all brackets and then take 
> any terms from the resulting expression with more than one CSP variable in 
> them and move them into a new expression, even if this is less efficient 
> than taking the original statement given and factoring that into multiple 
> expressions... ie solver would go:
> (A+1)(B+1)=0 to
> AB+A+B+1=0 to
> AB=C, C+A+B+1=0
> 
> rather than:
> (A+1)(B+1)=0
> C=A+1,D=B+1,CD=0.
> 
> 
> In all cases.. is this correct?

I was going to say no, it only multiplies out when one factor is a constant,
but looking at what IC actually does, if I'd said that I'd've been wrong.

I haven't thought much about nonlinear expressions, nor played with
different forms to compare their propagation strength, but I would expect
the second form you provide to be better than the first one.  Given that
figuring out the best form for nonlinears is (I believe) quite a difficult
problem, I would say that any constraint manipulation done by the compiler
ought to maintain what the user has written (in case the user deliberately
wrote it that way, e.g. for better propagation) unless it can be fairly sure
that the changes it makes are for the better.  IC (and probably other
solvers) doesn't appear to do this.

Any input on this subject welcome.

> I apologize if this is in the documentation but I was unable to find it and 
> wished to be sure I was correct.

Well, it's inherited from the behaviour of the linearize library, which is
documented, but doesn't explicitly say what it does in such cases (though
one of the examples provided shows it).

In another email you asked:

> Out of interest is there any kind of documentation available on how the ic
> library works which I would be able to acquire? I realise this is unlikely
> but thought that I would ask on the off chance.

There is some more detailed documentation than is provided in the manuals,
but:

- it's not really fit for public consumption

and

- the details are changing for every release

In particular, IC in the next release is expected to be quite different
"under the hood" than it is in the current release.

Cheers,
Warwick
Received on Wed Jan 15 14:37:04 2003

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:21 PM GMT GMT