Hi,
I just had the idea that maybe QuickXplain could take advantage of the afc
values, even if you don't have the link between propagators and high-level
constraints. Simply take the afc of the variables, and first try the
constraints that are linked to the variables with high afc.
Cheers,
Guido
Mikael Zayenz Lagerkvist wrote:
> Hi,
>
> Debugging failures in constraint programs is unfortunately a very hard
> problem. A main problem is that the reasons behind a failure to find
> solutions might be very global in nature. As a very simple example, think of
> a ring of less-than constraints (x1 < x2 < ... < xn < x1). There is obviously
> no solution, but the failure depends on all the constraints. Removing any one
> of the constraints gives a solution (given that the initial domains admit a
> solution that is).
>
> One possibility would be for you to implement something like QuickXplain [1],
> which was developed for use in an interactive configuration system. The main
> idea is to find a minimal set of constraints that gives no solutions by
> repeatedly finding constraints that when added lead to failure. If your
> problems are not too hard, then this is probably a good idea and reasonably e
> to implement.
>
> Another possibility, that is more akin to what you are asking, would be to
> use the afc. Afc stands for accumulated failure count, and is used for
> branching heuristics. It simply records the number of times each propagator
> has reported a failure. Note that the afc is a heuristic measure, in that
> there might be many propagators that would have reported failure, but only
> one does so. Unfortunately, while you can access all the propagators and get
> their afc (using the Propagators class), there is no way native to Gecode to
> connect the propagator instances with your model level constraints. That
> means that you would have to modify Gecode itself to use the afc.
>
> Cheers,
> Mikael
>
> [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.3472
>
>
> On Wed, Feb 24, 2010 at 8:51 PM, Adrian Secord <[email protected]> wrote:
> Hi, all:
>
> My colleagues and I are working on a user interface research project that
> uses Gecode internally to solve integer set problems. Our experiences with
> Gecode have been excellent; we are limited mostly by our lack of knowledge in
> the field of constraint programming.
>
> In our application, the constraints in our problems come from the user via a
> domain-appropriate user interface and we translate them into Gecode
> equivalents. The difficulty is that the user might specify constraints that
> lead to no solutions being found at all. Our users are not experts.
>
> What we'd like to do is give the user feedback about what they can do to best
> fix the situation, or possibly fix the situation for them. In particular,
> the constraints that come from the user are not necessarily set in stone --
> they are vague and messy, a problem with humans. ;) For our application, it
> is far better to ignore a constraint and come up with some solution than to
> not return a solution at all. The user can then adjust and iterate to get to
> a final solution.
>
> Is there some way to determine what was the "worst" or "tightest" constraint
> after a solution search failed? I'm looking for some indicator that
> constraint A was easy to satisfy while constraint B was difficult to satisfy.
> If we had that then we could suggest that the user drop B, or drop it
> automatically.
>
> I could probably do this crudely by iteratively dropping each constraint in
> turn and counting the number of solutions obtained, but this seems
> unsatisfying in many respects.
>
> Is something like this possible in Gecode? It's similar in some sense to the
> problem of soft constraints, but we don't need a full general solution.
>
> Any pointers or advice would be appreciated.
>
> Thanks!
>
> Adrian.
>
>
>
>
>
> _______________________________________________
> Gecode users mailing list
> [email protected]
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>
>
> --
> Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
> _______________________________________________
> Gecode users mailing list
> [email protected]
> https://www.gecode.org/mailman/listinfo/gecode-users
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
