« Comet version 1.1 | Main | Some of my models now at the Gecode/R site »

Some Comet constraint programming (CP) models

Earlier this week, I wrote about Comet in Comet version 1.1. For more about Comet, see the link mentioned above and newly created My Comet Page.

A year ago, when I first tested Comet, it was with the constraint-based local search module (LocalSolver, LS), but now I've modelled some of my standard problems in Comet's "classic" constraint programming module (CP). I hopefully will write more about local search modelling in Comet later.

Notes about constraint modelling in Comet

I really like working with Comet's constraint programming module (cotfd, finite domain). The comments below (and the models) should be read in the light that this is the first modelling using this CP module. There probably are other/better ways to do things.

My main experience with modelling in constraint programming is in MiniZinc so I use that system as a comparison.

The Comet models below were mostly translated from the MiniZinc models, and it was quite easy to do this translation, with some exceptions, e.g. the declaration of variables.

Comet has some features that I have really missed in MiniZinc:
- command line arguments and I/O. See minesweeper.co for an example.

- seamless conversion of floats and integers, and between integers and booleans.

- recursion. Well, I haven't have to use recursion in Comet yet, but it's nice to know it works.

- generating and colleting all solutions. Using exploreall all solutions to a problem may be obtained with in the model. In some of the MiniZinc solvers (Gecode and ECLiPSe) all solutions can be generated, but not collected in the model. Also, in Comet it is easy to modelling a problem with different input values (see send_more_money_any_base.co for an example).

- writing search heuristics. Search heuristics can be a real time saver. Comet supports writing your own labelling functions. I have not used this feature very much, but experimented with it in some models, e.g. langford.co (Langford's number problem). For my models, the built in labeling functions label or labelFF (first-fail) seems to be enough. The examples in the distribution use more advanced labeling techniques.

Comet is a big system, with many more features than those used in my first models, e.g. the local search, writing user defined constraints, tuples, classes etc etc.


In summary:
I have not found any great differences in speed, propagations etc between MiniZinc (and its solvers) and Comet, but these problems are not especially demanding, and I didn't the models. This would be a future work.

Comet is a great system and fun to use. I've now started to reread the book Constraint-Based Local Search by Pascal van av Hentenryck and Laurent Michel, about the constraint-based local search (LS module) in Comet, which has features that solve very large problems.


Code example


In Comet 1.1 two Comet models were shown. Here is some small examples of coding in Comet. Since I like recreational mathematics, let's convert between an array of numbers and an integer. 

function void toNum(Solver m, var{int}[] x, var{int} num, int base) {
  m.post(num == sum(i in 1..x.getSize()) base^(x.getSize()-i)*x[i]);
}

It is then used in the model using the Solver as argument like this, where we also constrain the integer variable z to 123. The output of x will - of course - be [0,0,1,2,3]

Solver m();

var{int} x[i in 1..5](m, Digits);

var{int} z(m, 0..100000);

exploreall {

  toNum(m, x, z, base);

  m.post(z == 123);

  } using {

    label(m);

    cout << x << endl;

}

This whole test model is toNum.co.

Here are two other function, alldifferent_except_0 , and increasing (enure that an array is sorted). Both are used in the model alldifferent_except_0.co.

function void alldifferent_except_0(Solver m, var{int}[] x) {

  int n = x.getSize();

  forall(i in 1..n, j in i+1..n) {    m.post(x[i] > 0 && x[j] > 0 => x[i] != x[j]);  }

}

function void increasing(Solver m, var{int}[] x) {
  forall(i in 2..x.getSize()) m.post(x[i-1] <= x[i]);
}

My Comet models

Below are some of my Comet models for (classic) constraint programming. Explanation of the problem, and references are in each specific file.

For all model, with one exception, the constraint programming module (CP) was used. The Coin grid, however, uses the mixed integer programming (MIP in the LP module). I first did a constraint programming variant but it was too slow (as where all the classic constraint programming models I've written in MiniZinc, Gecode/R etc). Integer programming really shines there.

So, here's the models.

Most of these models were translated from my models in other constraint programming systems, which see:


Posted by hakank on January 31, 2009 11:51 AM |