My Constraint Programming Blog: My first Gecode models

Gecode has long been an inspiration for many of my models: I have borrowed sample problems from its vast collection of examples, e.g. from Gecode's Minesweeper in the MiniZinc model minesweeper.mzn, from Gecode's Nonogram in the Comet model nonogram_regular.co and so on.

Since the Gecode models are very fast (one reason is that it use C++), they have also been used as a benchmark for my other models. For example, see the discussion about performance in Comet: Nonogram improved: solving problem P200 from 1:30 minutes to about 1 second. (The Gecode team later incorporated one of these findings in their Nonogram model.)

Gecode (and also the MiniZinc solver Gecode/FlatZinc) has a feature I like very much: it prints out much interesting statistics (note: almost all other systems I have used shows some sort of statistics). Here is an example of the output from the 1000-queens model (from the Gecode distribution):

Initial
propagators: 3
branchings: 1

Summary
runtime: 0.870 (870.000000 ms)
solutions: 1
propagations: 3006
nodes: 996
failures: 2
peak depth: 993
peak memory: 77721 KB

Using the Example framework (see below) makes it easy to interactively testing different strategies etc via the command line since there is a lot of default options to use. Here are the options for the queens model:

Options for Queens:

        -help, --help, -?

                print this help message

        -propagation (binary, mixed, distinct) default: distinct

                propagation variants

                  binary: only binary disequality constraints

                  mixed: single distinct and binary disequality constraints

                  distinct: three distinct constraints

        -icl (def, val, bnd, dom) default: def

                integer consistency level

        -solutions (unsigned int) default: 1

                number of solutions (0 = all)

        -c-d (unsigned int) default: 8

                recomputation commit distance

        -a-d (unsigned int) default: 2

                recomputation adaption distance

        -node (unsigned int) default: 0

                node cutoff (0 = none, solution mode)

        -fail (unsigned int) default: 0

                failure cutoff (0 = none, solution mode)

        -time (unsigned int) default: 0

                time (in ms) cutoff (0 = none, solution mode)

        -mode (solution, time, stat, gist) default: solution

                how to execute example

        -iterations (unsigned int) default: 500

                iterations per sample (time mode)

        -samples (unsigned int) default: 1

                how many samples (time mode)

        (unsigned int) default: 100

                which version/size for example

In Gecode version 3.0.1 and Gecode/FlatZinc 1.5 released I mentioned the Gist GUI for graphically exploring (and debugging) the search tree.

My Gecode models

Well, this week I started to program some Gecode models. I have created a special page for them: My Gecode page which - right now - contains the following models:

coins_grid.cpp: Placing coins on a grid (Tony Hurlimann)
Note: Constraint programming systems are not very good on this problem (at least not my models). Using integer programming is much faster, see Comet's MIP solver goins_grid.co).
diet.cpp: simple diet problem (operations research)
donald_gerald_robert.cpp: DONALD+GERALD=ROBERT, an experiment in "tweaking".
Note: Here I experiment in different search strategies, different branchings etc.
least_diff.cpp: Least diff problem, an alphametic puzzle: minimize the difference ABCDE-FGHIJ where A..J are integers 0..9 and all different.
map.cpp: Simple coloring problem (Van Hentenryck)
quasigroup_completion.cpp: Quasigroup Completion
send_more_money_any_base.cpp: SEND+MORE=MONEY in any base
seseman.cpp: simple recreational mathematics puzzle. See the CGI-program Seseman convent problem
seseman2.cpp: A more general model of the Seseman problem (using a matrix for representing the problem)
survo_puzzle.cpp: Survo puzzle (with just one hardcoded example)
xkcd.cpp: XKCD's knapsack problem. See the xkcd strip for the problem

Some notes about the models

These are all problems I tend to start with when learning constraint programming systems: they are all simple and different in some way or another. (Compare with other implementations in My MiniZinc page, My JaCoP page, My Choco page, My Gecode/R page, and My Comet page.)

My other implementations of Quasigroup Completion and Survo puzzle usually have some some data/problems files. Well, this time I was kind of lazy and just hard coded one example or two. Sorry about that.

As you may note my C++ is quite rusty, so some things could probably have been coded better. And to quote myself: I tend to program more for readabilty than elegance, which makes my programs sometimes look quite boring....

Example framework
The models use the Example framework mentioned above, which is the framework that all Geocde examples use. Unfortunately it is not completely incorporated in the Minimodel framework and is not mentioned in the (very good) introduction Modeling with Gecode (PDF). But since all Gecode's examples use the framework, almost all the questions I have had so far could be solve by just browsing the examples, with just a glance or two at the online documentation.

My Constraint Programming Blog

My first Gecode models

My Gecode models

Some notes about the models

See also

Post a comment