[gecode-users] Recovering gracefully from a failed solution

[Guido Tack]

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 <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/
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100226/eb0855b6/attachment.htm>