Thank you for the advice with Choco, i will have a look at, but currently i tend to use GeCode.
The work by Dechter et al uses a naive model, where CSPs are represented entirely by binary constraints which are given as lists of allowed pairs of values. In this setup, learning is relatively straightforward. In a realistic, propagation-based constraint solver, it is not. I finally managed to read "Dechter - Backjump-based backtracking for constraint satisfaction" and i think it is not restricted to Binary Constraints, because it is mentioned several times. And i have not found the list of allowed pairs in the paper, i thought of nogoods as set of domains, not explicit values. But i can not evaluate the possibilities, because i have no idea of how constraint solver do work. I hope the CSP community will have access to learning algorithms in the future, because i see a huge potential in them. By the way, can anybody say how the Benchmarks of the paper were made if no implementations exists of such solvers. I haven't found that in the text. Best regards, Max Ostrowski Guido Tack wrote: > Just as a quick follow-up, Choco used to have a feature called > explanations, which would probably do what you're looking for, but as > far as I understand, they have been removed from the current release. > > Cheers, > Guido > > Max wrote: > > >> At first am just forwarding my private mail contact with Guido Tack, >> as >> it may be interesting to other on the mailing list. >> >> Thank you for the answer. Its a pity that the learning techniques have >> not made it into CSP yet. >> I want to integrate a CSP solver into an ASP Solver, a reasoning >> system >> for logic programs. >> The advantage of learning from CSP solvers would be to get a good >> "reason" why literals/constraints can be propagated. SAT and ASP >> systems >> use a learning approach based on "reasons" and conflict-learning. So >> my >> system could use the reasons of the CSP solver to produce better >> conflicts and prune the search space. If it is not supported i will >> have >> to use a trivial reason, which means a constraint rule applies because >> of all other constraint rules the same variable occurs in. But this >> reason is not very specific and is not very applicable for >> backjumping. >> >> Maybe someone of the SMT (Sat Modulo Theory) area reads this message >> and >> can provide information on how this is done in SMT Solvers, as they >> incorporate CSP into SAT and using learning techniques. But all >> systems >> i found up to now seam to have written their own theory(CSP) solver. >> So if someone knows a CSP library capable of producing non trivial >> reasons and maybe doing conflict analysis, it would be great to post >> them here. Or maybe someone has an understaning how the SMT people do >> the things they do. >> >> Best regards, >> >> Max Ostrowski >> >> >> >> >> >> >>> Hi. >>> >>> Max wrote: >>> you probably already know me from the GeCode mailing list. >>> I just have a silly? question that i do not wanted to post on the >>> list. >>> It regards learning in gecode. >>> I'm not very familiar with constraint programming but it seems to me >>> that things like backjumping and conflict learning already made it >>> into the current CSP systems. >>> Found a paper: Backjump-based backtracking for constraint >>> satisfaction >>> problems by Rina Dechter and Daniel Frost >>> >>> So, does GeCode really not support learning and backjumping? Because >>> these features seem to be necessary for my diploma thesis and gecode >>> seems to be a state of the art CSP solver and one of the best >>> looking. >>> So my first question would be: Why it is not supported? - and my >>> second barefaced question- : Do you know a similar CSP lib where it >>> is >>> supported? >>> >> It is not supported (and won't be in the near future), because no one >> knows how to do it properly. The work by Dechter et al uses a naive >> model, where CSPs are represented entirely by binary constraints which >> are given as lists of allowed pairs of values. In this setup, >> learning >> is relatively straightforward. In a realistic, propagation-based >> constraint solver, it is not. >> That also answers your second question: I don't know of any realistic >> library that does learning. None of the commercial packages (ILOG >> Solver, SICStus Prolog, B-Prolog) incorporates learning, nor does >> any of >> the other free libraries like Choco or Minion. The closest you can >> get >> is the work on "Propagation = Lazy Clause Generation" >> (http://www.cs.bgu.ac.il/~mcodish/Papers/Pages/cp07.html), this is the >> most promising attempt at using SAT learning technology for CP >> solving I >> know of (but it's quite different from classic CP solvers). >> >> Btw, you can ask questions like this on the mailing list, no problem. >> It's about why we do/don't do certain things, so it definitely fits! >> Maybe you can elaborate how learning is important for what you want >> to do. >> >> Cheers, >> Guido >> >> _______________________________________________ >> 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 > > _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users