[gecode-users] Diagnosing failures

[Malcolm Ryan]

On 19/11/2007, at 9:34 PM, Christian Schulte wrote:

> Hi,
>
> To give you an idea, take the following, rather small, examples  
> (they are
> included in Gecode).
>
>  - Alpha, 21 propagators, 26 variables: 123 919 propagator executions
>  - Golomb rulers 10, 55 variables, 46 propagators: 3 482 588  
> propagator
> executions
>  - Magic squares 7, 49 variables, 19 propagators: 9 596 013 propagator
> executions

I see. Yes, that is a lot.

> So that's quite something. And most of the propagator executions  
> are not
> really interesting. While debugging is difficult, and there is  
> little known
> how to do it, the level of abstraction of looking at a single  
> propagator is
> not really feasible.

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.

> Typically there is a pretty close mapping between a constraint and the
> propagator implementing the constraint. But not always and  
> typically not
> after some propagations (propagators typically rewrite themselves).
>
> Gecode 2.0 comes with a reflection layer that in principle allows  
> you to get
> to know everything about a space, but I do not know whether this  
> will be
> available in Gecode/J. Also, I would doubt that the amount of  
> information is
> useful.
>
> But what helps a lot is using Gist as said. It will at least tell  
> you the
> results of propagation before branching. Just printing before and  
> after
> propagation is also not too bad.

Gist is great for visualising the search, but as you say, there are  
many constraint propagation steps between one search step and the next.

> Sorry that I cannot be more helpful than that.

That's okay. I appreciate that it is not a solved problem. I'm just  
throwing around some ideas. Maybe I'll try them out myself, if I find  
time.

Malcolm

--
      "The act of defending any of the cardinal virtues has today all
       the exhilaration of a vice."
                                     - G.K.Chesterton A Defense of  
Humility