[gecode-users] Recovering gracefully from a failed solution

[Adrian Secord]

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.