[gecode-users] Clockwise constraint

[Malcolm Ryan]

Hrm, it seems that the extensional version is going to be inordinately  
large. How hard would it be to write a propagator for this specific  
constraint X = (A < B < C)?

If X is known, it can simply devolve into atomic constraints.
If X is unknown, it would just need to check that there exists b in  
dom(B) such that min(A) < b < max(C), to be re-computed whenever  
min(A), dom(B) or max(C) changed. If we kept the smallest value of b  
between propagations the amortised cost of the computation could be  
small.

How would I go about adding this to Gecode/J?

Malcolm

On 02/06/2008, at 7:03 PM, Guido Tack wrote:

> Malcolm Ryan wrote:
>
>> On 02/06/2008, at 5:18 PM, Guido Tack wrote:
>>>
>>> Oh, I somehow didn't see that it's always ternary!  In that case you
>>> might really want to try the extensional constraint.  Just implement
>>> a generator that lists all allowed tuples.
>>
>> Nice idea, but really not viable. In practice the domains are much
>> larger than 4 (more like 100), and the table size would be O(n^3).
>
> We just tried it (just for fun ;-), and for domain size 100 it's  
> just under 500 000 tuples (which takes about 10M of memory).  For  
> domain size 200 it's around 4 000 000 tuples, which is still  
> manageable with under 100M of memory.  Generation takes less than a  
> second.
>
> Even if you use more than one of these propagators, you can reuse  
> the same table for each one.  So, you might actually want to try  
> this, it may work!
>
> Cheers,
> 	Guido