[gecode-users] Clockwise constraint

[Guido Tack]

Malcolm Ryan wrote:

> On 03/06/2008, at 6:40 PM, Guido Tack wrote:
>>
>>> If we kept the smallest value of b
>>> between propagations the amortised cost of the computation could be
>>> small.
>>
>> That wouldn't help, because you cannot start checking for values
>> starting from that previous smallest value.
>
> Why not? Most of the time the old value of 'b' will still be a valid
> solution. If it isn't, we know that none of the smaller values are
> solutions so we should be able to count upwards from there (or jump
> straight to min(B), if b < min(B)). Ie, something like:
>
>    if (B.min() > A.max() && B.max() < C.min()) {
>       // set X = true
>    }
>
>    if (!B.in(b)) {
>       b = B.min();
>    }

The problem is here: testing B.in(b) is linear time, so it's just as  
expensive as finding a new b.

> Wouldn't that work? Or am I making some incorrect assumptions about
> the data available to propagators?

It would work (I didn't check in detail, though), but it wouldn't be  
any more efficient, so why not go for the simple version ;-)

>
>>> How would I go about adding this to Gecode/J?
>>
>> Unfortunately, we just found out that one important ingredient for
>> reified propagators currently does not work in Gecode/J: you cannot
>> return ES_SUBSUMED from a propagator (which you need in order to
>> rewrite into other propagators).  So I'm afraid currently the only
>> option is to add the propagator in C++ and then interface it to Java.
>
> That was what I had in mind. I remember you saying previously that the
> Java Propagator class is not suitable for "real" problems.

Ok, great.  If you need help with writing the propagator, or with  
interfacing it to Java, let us know!  I'd start by looking at the  
propagate function of ReEqDom in gecode/int/rel/eq.icc for an example  
of a C++ reified propagator.

Cheers,
	Guido