My Constraint Programming Blog

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.

• 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
  

Later on, the following problems has been useful and rewarding to model early.

• 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
  

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.