[gecode-users] Operation of precede constraint on array of sets

[Tim Potter]

Thanks Chris and Sebastian for your replies.  I agree that your parsing of the mathematical description of the constraint is valid but I don't think the result is in the spirit of the constraint, as much as I can divine this from the documentation.  

"Value precedence constraints over set variables enforce that a value pieces another value in a set of array variables" is the overview of the precede() constraint in Modelling and Programming with Gecode.  Surely if there is any case where the first value is not placed before, i.e is preceded by, the second then there doesn't seem to be any point to the constraint.

I think I'll dive into the source code and test case to try and get some more insight.

(I forgot to mention in my original message that the constraint is documented in MPG, p.93).


Thanks,

Tim.

> On 27 Nov 2017, at 11:45 am, Chris Mears <chris at cmears.id.au> wrote:
> 
> Hello Tim,
> 
> I think you might be misreading this version of the constraint. The constraint means "if s and t are ever treated differently -- that is, if there's a set where one of them is present but not the other -- then you'll get a set with only s before you get any set with only t." So your example satisfies the constraint because s and t are always either both present or both absent.
> 
> Cheers,
> Chris
> 
> 
> On 25 November 2017 at 08:38, Tim Potter <tpot at frungy.org> wrote:
> Hi everyone.  I hope this isn't some silly misunderstanding but I'm having trouble figuring out how the precede() constraint works when applied to SetVarArray.
> 
> Imagine I have a set of tasks with dependencies, for example 1->2, 2->3 and 3->4 to keep things simple.  I've added the following constraints:
> 
>     // Array of sets of integers from {1..4}
> 
>     SetVarArray deps(*this, 4, IntSet::empty, IntSet(1, 4));
> 
>     // Enforce pairwise disjointedness
> 
>     sequence(*this, deps);
> 
>     // Final task must appear
> 
>     rel(*this, setunion(deps) >= IntSet(IntArgs(1, 4)));
> 
>     // Task ordering constraints
> 
>     precede(*this, deps, 1, 2);
>     precede(*this, deps, 2, 3);
>     precede(*this, deps, 3, 4);
> 
> Now this should produce at least a solution like {{1}, {2}, {3}, {4}}.  However I get this as my first solution in the output:
> 
>         {{1..4}, {}, {}, {}}
> 
> which indicates that the precede() constraint is not behaving as I think it should.
> 
> According to to the documentation the precede(home, x, s, t) version of the value precedence constraint as applied to set variables says that s is not an element of x_j and t is an element of x_j, then i < j such that s is an element of x_i and t is not an element of x_i.
> 
> I don't understand how the solution above satisfies the above unless maybe the i < j is really acting as i <= j.  This seems to be the case based on the other solutions as they're sorted but that could be a side effect of the sequence() constraint.
> 
> Does anyone know what I'm doing wrong here?
> 
> 
> Thanks,
> 
> Tim.
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>