[gecode-users] Red square syndrome

[Mikael Zayenz Lagerkvist]

Hi,

Debugging constraint programs is unfortunately a very hard problem. There
has been some research on how to better support debugging with tools and
techniques, but not that much that has matured into real usable products.

In my opinion, having a graphical search engine such as Gist is a really
important first step. Another thing that could become important is S-boxes
[1], where sets of constraints can be grouped to make tracing execution
feasible. S-boxes can be simulated with groups [2], and I hope that a usable
version of groups will be added to Gecode this year. That doesn't help you
right now though.

When I write a model that seems to give a failure even though it shouldn't,
my general technique is to try to comment out parts of the model so that I
can find a small subset of constraints that still give the failure. This is
then easier to reason about. Trying the model on small instances first is
also a good idea.

One thing to note is that a propagator doesn't really need to remove all
values from a domain to detect failure. It could for example run a check for
some necessary criteria, and when that fails the propagator fails
immediately. One example could be a distinct propagator that checks if the
union of all its variables domains contain enough distinct values (not that
distinct in Gecode actually does it this way).

Hope this helps,
Mikael

[1]
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.1727&rep=rep1&type=url&i=1
[2] http://web.it.kth.se/~cschulte/paper.html?id=LagerkvistSchulte:CP:2009

On Wed, Jan 20, 2010 at 9:12 AM, benoit <benoitlaurent at neuf.fr> wrote:

> Dear All,
>
> I have been using Gecode for a few months now and often struggle hard to
> debug my models. I have many different types of constraints and I encounter
> difficulties to understand failures. My question is the following : is there
> a general good practice or is it too problem-dependant ?
>
> I am using Gist of course and implemented my own branching strategies to
> record the variable-value pair currently considered (integer modeling). But,
> still, it remains difficult for me to identify domains that "would" become
> empty and the reason why (even if "variable domains are never empty").
>
> Thank you in advance for your help
>
> Benoît
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>



-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100120/94321dda/attachment.htm>