[gecode-users] Diagnosing failures

[Mikael Zayenz Lagerkvist]

On Nov 21, 2007 12:14 AM, Malcolm Ryan <malcolmr at cse.unsw.edu.au> wrote:
> Clearly not. But neither do you want to inspect all the machine
> operations in a standard program. Some abstraction is necessary. The
> S-boxes idea is a good start. Grouping the variables into meaningful
> structures (i.e. objects) could also help. And then you have causal
> relations between propagator executions, don't you? Ie, propagator X
> fired, constraining variable V, which in turn caused propagator Y to
> fire. If you could visualise the causation graph at a level of
> abstraction, you'd have the beginnings of a useful tool.

What causes a propagator to do some propagation might not be so simple
as you describe. Typically, a propagator will have many variables it
subscribes to, and several of them might be modified. Furthermore, the
variables might be modified by different propagators, or a variable
might be modified several times by a single propagator (due to
priorities).

Even harder, even if there is only a single modification to a variable
x that makes propagator P run, it might not be the only relevant
modification for the result of the propagation of P. Here is a small
example of this.


Variables: x={1,2,3,4}, y={1,2,3,4}
Propagators: P1 (x!=3), P2 (y>=3), and P3 (y==x)
P1 and P2 are currently scheduled for execution, but P3 is not.
Furthermore, P3 is a bounds-consistent equality propagator (thus it
only reasons on the bounds of variables).

In the first step, P1 runs. This gives the domains x={1,2,4},
y={1,2,3,4}. Nothing changes in the bounds of x and y, which means
that P3 is not going to be scheduled.

In the second step, P2 runs. This gives the domains x={1,2,4},
y={3,4}, and P3 is scheduled for propagation (the bounds of y has
changed).

In the third step, P3 runs giving the domains x={4}, y={4}.

The removal of 3 from the domain of y by propagator P3 is not "caused"
by P2 in some sense, even though this is the only propagator that made
modifications that made P3 runnable. Instead it is caused by the
modifications done by P1, which -at the time they were done- were not
relevant to P3.


I hope this explains the complexity of causation a little more.

Cheers,
Mikael

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