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 _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
