[gecode-users] Propagator

[Mikael Zayenz Lagerkvist]

Hi,

I'll answer the questions about cumulatives here, since I implemented
it originally. Your two questions are related in that they both are
caused by the fact that the propagation-algorithm for cumulatives is
not idempotent.

On Mon, May 25, 2009 at 3:16 PM, Jan Kelbel <kelbelj at fel.cvut.cz> wrote:
> My second question (set of questions) is related to Val propagator for
> cumulatives constrait, which is my study material for implementation of
> scheduling constraints.
> 2) Why there is no ES_FIX return from the Val::propagate() method?
> In the documentation is that when the propagator computes fixpoint, it
> should return ES_FIX.
> Is the reason that checking whether fixpoint is reached is expensive,
> and the propagation scheduler arranges that the propagation is not
> executed too many times?

Checking for a fix-point for cumulatives amounts to re-running the
propagation algorithm and seeing if there were any changes. Since the
algorithm is comparatively expensive, it is better to defer
re-execution to later than to run the algorithm in a loop to find a
local fix-point.


> 1) in Val::propagate()  file cumulatives/val.hpp
> at line 276 there is a test if all the variables are assigned. Is there
> a reason why in case of subsumed = true; the function ES_SUBSUMED() is
> called  as late as at line 386?

The reason is that subsumed should only be returned from this
particular propagator if the propagation algorithm does not detect
failure when all the variables are assigned before the algorithm is
executed. If the algorithm was idempotent, then the check for assigned
values could be done after the main algorithm.


Cheers,
Mikael

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