[gecode-users] Operation of precede constraint on array of sets
Chris Mears
chris at cmears.id.au
Mon Nov 27 01:45:52 CET 2017
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20171127/623ef4c6/attachment.html>
More information about the users
mailing list