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:
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.
- 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)
- SEND+MORE=MONEY or n-queens
* learning how to handle the CP system. See above.
- Least Diff
* minimize the difference ABCDE - FGHIJ (digits all distinct)
* this was actually my first "real" (i.e. non-standard) constraint programming problem
* how to optimize (here minimize) a solution
MiniZinc: least_diff.mzn
Choco: LeastDiff2.java
JaCoP: LeastDiff.java
Gecode/R: least_diff.rb
Comet: least_diff.co
Gecode: least_diff.cpp
- Diet
* simple OR problem
* how to interact with integer arrays and variable arrays
MiniZinc: diet1.mzn
Choco: Diet.java
JaCoP: Diet.java
Gecode/R: diet.rb
Comet: diet.co
Gecode: diet.cpp
- Seseman
* one of my earliest constraint programming (modeled in ECLiPSe)
* generating one or all solutions
* handling of matrices
MiniZinc: seseman.mzn
Choco: Seseman.java
JaCoP: Seseman.java
Gecode/R: seseman.rb
Comet: seseman.co
Gecode: seseman.cpp
- Coins grid
* Tony Hubermann's grid puzzle, minimize distances in the grid
* how does a CP system handle this MIP problem (mostly quite bad compared to MIP)
MiniZinc: coins_grid.mzn
Choco: CoinsGrid.java
JaCoP: CoinsGrid.java
Gecode/R: coins_grid.rb
Comet: coins_grid.co
Gecode: coins_grid.cpp
- de Bruijn sequence
* a personal favorite
* see how large problem an implementation can handle
* command line options to the model
MiniZinc: debruijn_binary.mzn
Choco: DeBruijn.java
JaCoP: DeBruijn.java
JaCoP: DeBruijnIterate.java (alternative version generating arbitrary number of solutions)
Gecode/R: debruijn_binary.rb
Comet: debruijn.co
Gecode: debruijn.cpp
- alldifferent_except_0
* how to implement a (decomposition of a) global constraint
* logical operators on variables: implication (if then), &&, !=
MiniZinc: alldifferent_except_0.mzn
Choco: AllDifferentExcept0_test.java
JaCoP: AllDifferentExcept0_test.java
Gecode/R: all_different_except_0.rb
Comet: alldifferent_except_0.co
Gecode: alldifferent_except_0.cpp
- Furniture Moving
* scheduling, the cumulative constraint
* not in all systems (Gecode and Gecode/R)
MiniZinc: furniture_moving.mzn
Choco: FurnitureMoving.java
JaCoP: FurnitureMoving.java
Gecode/R: N/A
Comet: furniture_moving.co
Gecode: N/A
- Mineswepeer
* more advanced example (quite simple to implement, though)
* reading problems from a file or handling different problems in some other way
MiniZinc: minesweeper.mzn
Choco: MineSweeper.java
JaCoP: MineSweeper.java
Gecode/R: minesweeper.rb
Comet: minesweeper.co
Gecode: N/A (No Gecode model since there is one in the Gecode distribution)
- Quasigroup Completion
* yet another grid puzzle/problem
* alldifferent on rows/columns * handling matrices
* handling of different problems (file or some other way)
MiniZinc: quasigroup_completion.mzn
Choco: QuasigroupCompletion.java
JaCoP: QuasigroupCompletion.java
Gecode/R: quasigroup_completion.rb
Comet: quasigroup_completion.co
Gecode: quasigroup_completion.cpp
- Survo puzzle
* yet another grid puzzle
* handling of different problems (file etc)
MiniZinc: survo_puzzle.mzn
Choco: SurvoPuzzle.java
JaCoP: SurvoPuzzle.java
Gecode/R: survo_puzzle.rb
Comet: survo_puzzle.co
Gecode: survo_puzzle.cpp
- Young Tableaux and partitions
* combinatorial problem, easy to state and sometimes tricky to model
MiniZinc: young_tableaux.mzn
Choco: YoungTableuax.java
JaCoP: YoungTableuax.java
Gecode/R: N/A
Comet: young_tableaux.co
Gecode: young_tableaux.cpp
- Send Most Money in any base
* learning how to get parameters to the program (command line)
* in some versions: first optimize, then generating all solutions
MiniZinc: send_more_money_any_base.mzn
Gecode/R: send_more_money_any_base.rb
Comet: send_most_money.co
Comet: send_most_money2.co
Gecode: send_more_money_any_base.cpp
- simple map coloring
* using graph/matrix
* optimization
MiniZinc: map.mzn
Comet: map.co
Gecode/R: map.rb
Gecode: map.cpp
- nonogram
* fun problem
* testing different search strategies
* using "real" regular expressions (Gecode/R)
* using global constraint regular (MiniZinc/Comet)
MiniZinc: nonogram.mzn
Gecode/R: nonogram.rb
Comet: nonogram_regular.co
- xkcd
* simple problem (easy to understand)
* knapsack / set covering
MiniZinc: xkcd.mzn
Comet: xkcd.co
Gecode/R: xkcd.rb
Gecode: xkcd.cpp
- Crosswords
* very simple crossword example
* using strings/chars (instead of ints)
* a study in non-trivial Element constraint (array/matrix access)
MiniZinc: crossword.mzn
Choco: CrossWord.java
JaCoP: CrossWord.java
Gecode/R: N/A
Comet: crossword.co
Gecode: crossword.cpp
- Word square
* continue from Crosswords
* a study in another non-trivial Element (actually simpler than for Crosswords)
* how to read a file (the word list)
MiniZinc: word_square.mzn
Choco: WordSquare.java
JaCoP: WordSquare.java
Gecode/R: N/A
Comet: word_square.co
Gecode: word_square.cpp
- Who killed Agatha?
* logical problem
* reification
* Element constraint
MiniZinc: who_killed_agatha.mzn
Comet: who_killed_agatha.co
Gecode: who_killed_agatha.cpp
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
Posted by: Geoffrey De Smet | May 9, 2009 11:34 AM
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...
Posted by: hakank | May 9, 2009 11:55 AM