[gecode-users] Unary and Cumulative constraints

[Mikael Zayenz Lagerkvist]

On Fri, Aug 13, 2010 at 9:46 AM, Guido Tack <tack at gecode.org> wrote:
>> you are right, it should be 'implied reification' and yes it is unnecessary
>> overhead to post e = p + s for each propagator but it would also give
>> you some more control on scheduling or not scheduling the propagator
>> on deltas on e,p or s.  Perhaps not much to gain.

Scheduling and executing a propagator for e=p+s is actually very very
cheap. I would expect that trying to use deltas to control scheduling
is not worth it at all, doing the check would almost equal all the job
anyway.

> When you have hundreds of tasks, propagator scheduling might actually
> become important.  But I think I'll start with the simple version, and then
> see if there is a problem.

Just to expand on what Guido is saying, the issues one might encounter
for a large set of propagators that have variables in common, is that
one might get a bad order for the propagator executions. Lets take a
worst-case example from [1] as an illustration. Given a sequence of
propagators
 x1 < x2 < x3 < ... < xn
for variables with domains {1..n}, most systems will require O(n²)
propagation steps to find infeasibility. Using the best propagation
order, it only takes O(n). Such pure cases of degenerate behavior are
fortunately not very common.

Cheers,
Mikael

[1] Propagator Groups, Mikael Z. Lagerkvist and Christian Schulte. CP
2010. http://www.ict.kth.se/~zayenz/papers/LagerkvistSchulte_CP_2009.pdf

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/