« Comet: version 1.2-rev2 released and a facelift of the site | Main | Learning constraint programming - part II: Modeling with the Element constraint »

Learning constraint programming (languages) - part I

While preparing for My talk at SweConsNet Workshop 2009: "Learning Constraint Programming (MiniZinc, JaCoP, Choco, Gecode/R, Comet, Gecode): Some Lessons Learned", I plan to blog about summarizations, findings etc.

This part is a description of the problems I tend to start modeling in a new constraint programming system.

First run
The first model to run is probably SEND+MORE=MONEY or n-queens, since either one of them are distributed in the package. This is to make sure that the system works, environment variables are correct, compilation works, how is the constraints and search strategies stated in the system, what to expect in terms of output, etc.

First models
If either SEND+MORE=MONEY or n-queens is not in the distribution (which would be a surprise), I start with that model.

The models
The models below are all the first problems I start with, sorted in the way they usually are implemented. Also there is a a short explanation what is learned about the system. After all these models are done, or a larger part of them, I publish them at a My [CP System] Page..

The list is very personal and may not be suited for everybody (if anyone, except me). One reason is that my goal has been to learn about modeling problems using constraint programming, and not so much about implementing propagators etc (and that is why I tend use decompositions a lot). However, lately I have somewhat shifted the focus to more gory details.

Also, I think it is important that when learning new stuff (especially by oneself) is to use examples that are well known, fun, and perhaps even with a personal history. Some examples of this "personal attachment" of a problem:
  • The Least Diff problem was a problem in a company competition 1998 and was actually one of my inspiration to start learning constraint programming. The first version was programmed in a Prolog system, SICStus Prolog.
  • Seseman problem: this was a problem stated by a fellow blogger in 2005, and I blogged about (in swedish) in Sesemans matematiska klosterproblem samt lite Constraint Logic Programming).
  • de Bruijn sequences is a personal favorite problem since long time.
  • etc.
The implementations are sorted in (approximately) the order I start to learn the systems.
  • MiniZinc (feb 2008)
  • Choco (first "touch" in 2006, and then more in september 2008)
  • JaCoP (august 2008)
  • Gecode/R (january 2009)
  • Comet (local search module 2007, constraint programming module: january 2009)
  • Gecode (march 2009)
Note: Before 2008 I have sporadically studied (played) with some Prolog systems with support for constraint logic programming, e.g. ECLiPSe and SICStus Prolog, and also with some other CP-systems (e.g. OPL, XPress, ESSENCE'/Tailor/Minion) but not at all that systematic as with the systems mentioned in the list above. Later on, the following problems has been useful and rewarding to model early. Note: The two problems Crosswords and Word square has not been published before, and I plan to blog more about the findings when modeling these "non-trivial Element" models.

Comments

Have you tried any of these examples on drools-solver? Finding a solution to nqueens is one of it's examples.

You can find the latest manual here:
https://hudson.jboss.org/hudson/job/drools/lastSuccessfulBuild/artifact/trunk/target/docs/index.html

Geoffrey: I haven't tried drools with these examples, but did played with drools in 2007 (not the solver, though).

Thanks for the suggestion and link. I will put drools-solver on the list to check out more. There are other constraint programming systems (and other paradigms such as Answer Set Programming) that already are in that list...

Post a comment

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)