[gecode-users] Unary and Cumulative constraints

[Guido Tack]

David Rijsman wrote:
> would it make more sense to always propagate when mandatory argument is not part of the argument list. When we allow a task not to be mandatory only enforce s = p + e when mandatory becomes true and make mandatory false when s = p + e can no longer be enforced (reify s = p + e on mandatory)? 

The algorithms already perform the latter reasoning, i.e., if a propagation on the start or end time of an optional task would result in failure, the task is excluded.

I think one would have to use "implied reification", i.e., m -> s+p=e, where m is the mandatory flag (you don't want s+p!=e for an excluded task).  And there is potential for more propagation.  In [1], the temporal constraints can be propagated even for optional tasks. E.g., if two tasks A and B are optional, and A is present if and only if B is present, and if A and B are present, then A is before B, we can always propagate e(A)<=s(B), even before it is determined if A and B are actually present.  We cannot repeat this kind of reasoning for every resource.  Instead, we need a centralized data structure that stores the temporal information, and a propagator for the global temporal constraint.

> This way we can model a task which can require one or more resources using the sum of the mandatory variables for the different constraints as the minimum and maximum constraints without having to worry about the temporal constraints within a task?

I don't think this solves the problem.  Assume a mandatory task that requires a certain tool, of which we have two, as well as a skilled worker.  Then that task would be on a cumulative constraint with capacity 2 for the tool, and on a unary constraint for the worker (assuming he's not a great multi-tasker).  If both propagators propagated s+p=e, there would be an unnecessary overhead.

The s+p=e propagation is a matter of having a nice modeling API (which we will provide, eventually).  The current interface is designed to include no "magic", so that the modeler has full control over which propagators actually get posted.

Cheers,
	Guido

[1] P. Laborie and J. Rogerie. Reasoning with conditional time-intervals. In D. Wilson and H. C. Lane, editors, FLAIRS Conference, pages 555–560. AAAI Press, 2008.

-- 
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/