My Constraint Programming Blog

The other day the constraint-based local search system Comet version 1.1 was released.

The release contains the following new features (mailed to the mailing list, and slightly edited):

Dynadec is proud to announce Comet Release 1.1. New features in thi rrelease include:
* Addition of a priority to user-defined constraints.
* Addition of the function sqrt for the local solver.
* Addition of the method "tryPost" on the CP solver for postin constraints in user-defined constraints.
* Addition of the total number of failures (i.e., across restarts).
* Addition of a method startWithRestart to start LNS with a restart which may generate an initial solution.
* Function minAssignment now includes an alldifferent and a computation of the cost
* Added the ability to select from a set of strings
* Added a onFailure clause to select to handle elegantly the case where no value is selected
* Text based debugger on all platforms. (-gtext)
* GUI for debugger on OSX and Linux (-ggui) [experimental]
* C++ API: with good packaging

We encourage all current customers and evaluators to download the latest at http://www.dynadec.com/support/downloads/index.php

The distribution includes 18 examples of using Comet with three different paradigms (modules):
* constraint-based local search
* traditional constraint programming
* linear programming

It also contains detailed descriptions of the API (HTML).Note that the distribution is now via Dynadec, not Comet online (which links to an older version).

An earlier version of Comet is documented in the great book Constraint-Based Local Search by Pascal van av Hentenryck and Laurent Michel, the main developers of Comet.The book explains Comet and the principles of constraint-based local search very well, and I really recommend it. The newer development of Comet have been published in papers by the Comet developers, see Publications. (By the way, I also recommend Van Hentenryck's classic and pathbreaking book "Constraint Satisfaction in Logic Programming", which was my second read in this field, and I still enjoy re-reading it.)

I like Comet, but have been somewhat frustrated when the version 1.02 (the former version) broked older code (sometimes only slight changes was needed, though)), but now it has been stabilized. In the future I hope to come back with some of my own models.

Example: N-queen
As can been seen from the examples below the Comet language is quite C++-ish (or maybe rather OPL-ish?).

Here is two model of the n-queens problem. First using constraint-based local search (the example ls/queens.co)

import cotls;

int t0 = System.getCPUTime();

Solver m();

int n = 16;

range Size = 1..n;

UniformDistribution distr(Size);

var{int} queen[Size](m,Size) := distr.get();

ConstraintSystem S(m);

S.post(alldifferent(queen));

S.post(alldifferent(all(i in Size) queen[i] + i));

S.post(alldifferent(all(i in Size) queen[i] - i));

m.close();

int it = 0;

while (S.violations() > 0 && it < 50 * n) {

   selectMax(q in Size)(S.violations(queen[q]))

      selectMin(v in Size)(S.getAssignDelta(queen[q],v))

         queen[q] := v;

   it++;

}

cout << queen << endl;

It solves the 1000-queens problem in about 1.5 seconds.

Here is the same problem, using the (traditional) constraint programming module (the example cp/queens.co)

import cotfd;

Solver m();

int t0 = System.getCPUTime();

int n = 8; //1000;

range S = 1..n;

var{int} q[i in S](m,S);

Integer np(m.getNPropag());

cout << "Initiating search..." << endl;

Integer c(0);

solveall {

   m.post(alldifferent(all(i in S) q[i] + i),onBounds);

   m.post(alldifferent(all(i in S) q[i] - i),onBounds);

   m.post(alldifferent(q),onBounds);

} using {

   forall(i in S) by (q[i].getSize()) { // : !q[i].bound()) by (q[i].getSize()) {

      tryall(v in S : q[i].memberOf(v))

         label(q[i],v);

   }

   c := c + 1;

}

cout << "Nb : " << c << endl;

int t1 = System.getCPUTime();

cout << "Solution = " << q << endl;

cout << "time: " << t1 - t0 << endl;

cout << "#choices = " << m.getNChoice() << endl;

cout << "#fail    = " << m.getNFail() << endl;

cout << "#propag  = " << m.getNPropag() - np << endl;

Also see
Dynadec
Download Comet
Dyandec forums (Dynadec)

Comet online
publications, which contains many publications about Comet
mailing list
Wiki. Note: the wiki have not been updated for a while. For documentation about the API, see the documentation in the distribution.