[gecode-users] Clockwise constraint

[Malcolm Ryan]

What I need is a reified version of the pairwise rel(). Then I could  
say:

a < c --> a < b < c
b < a --> b < c < a
c < b --> c < a < b

Since there is no value of 'a' that satisfies c < a < b, it would have  
to deduce that b < c.

Representing this as (c < a) and (a < b) is not good enough, as there  
are possible values of 'a' to satisfy each of the inequalities  
individually, just not both together.

On 02/06/2008, at 4:10 PM, Malcolm Ryan wrote:

> I want to make a constraint which represents the order of three values
> around a ring.
>
> Eg: if we have a,b,c \in {1,2,3,4} then I want to represent the
> constraint:
>
> clockwise(a,b,c) == (a < b < c) or (b < c < a) or (c < a < b)
>
> I can construct this directly using BExprs, but the use of 'or' means
> that it doesn't propagate very well. Eg:
>
>         BExpr beLessAB = new BExpr(a, IntRelType.IRT_LE, b);
>         BExpr beLessBC = new BExpr(b, IntRelType.IRT_LE, c);
>         BExpr beLessCA = new BExpr(c, IntRelType.IRT_LE, a);
>
>         BExpr beABC = new BExpr(beLessAB).and(beLessBC);
>         BExpr beBCA = new BExpr(beLessBC).and(beLessCA);
>         BExpr beCAB = new BExpr(beLessCA).and(beLessAB);
>
>         BExpr clockwise = beABC.or(beBCA).or(beCAB);
>
>         Gecode.post(test, clockwise);
>         Gecode.rel(test, test.a, IntRelType.IRT_NE, 2);
>         Gecode.rel(test, test.a, IntRelType.IRT_NE, 3);
>         Gecode.rel(test, test.b, IntRelType.IRT_NE, 1);
>         Gecode.rel(test, test.b, IntRelType.IRT_NE, 4);
>         Gecode.rel(test, test.c, IntRelType.IRT_NE, 1);
>         Gecode.rel(test, test.c, IntRelType.IRT_NE, 4);
>
> Will give a = {1,4}, b = [2..3], c = [2..3] when it should be able to
> deduce that b = 2, c = 3. Is there any other way to represent this so
> that the propagation works better?
>
> Malcolm
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users