[gecode-users] Recovering gracefully from a failed solution

[Mikael Zayenz Lagerkvist]

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 <ajsecord at cs.nyu.edu> 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
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>



-- 
Mikael Zayenz Lagerkvist,
http://www.ict.kth.se/~zayenz/<http://www.ict.kth.se/%7Ezayenz/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100226/4cc46677/attachment.htm>