### 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(Solverm, 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]`

Solverm();

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(Solverm, 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(Solverm, 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.

- alldifferent_except_0.co: Global constraint all_different except 0

- coins_grid.co: Placing coins on a grid (Tony Hurlimann), using the LP module (see comment above)

- country_cp.co: Simple map coloring problem.

- debruijn.co: de Bruijn sequences, both "classic" and "arbitrary"

- diet.co: simple diet problem (operations research)

- donald_gerald.co: Alphametic puzzle DONALD + GERALD = ROBERT

- langford.co: Langford's number problem (CSPLib problem 24)

- least_diff.co: Least diff problem, an alphametic puzzle, minimize the difference ABCDE-FGHIJ where A..J is integers 0..9 (all different)

- lichtenstein_coloring.co: Coloring the communes of Lichtenstein

- minesweeper.co: Minesweeper problem.

Problem files for the Minesweeper program. Usage:`comet minesweeper.co problem file`

- Problem 0 from Gecode minesweeper.cc

- Problem 1 from Gecode minesweeper.cc

- Problem 2 from Gecode minesweeper.cc

- Problem 3 from Gecode minesweeper.cc

- Problem 4 from Gecode minesweeper.cc

- Problem 5 from Gecode minesweeper.cc

- Problem 6 from Gecode minesweeper.cc

- Problem 7 from Gecode minesweeper.cc

- Problem 8 from Gecode minesweeper.cc

- Problem 9 from Gecode minesweeper.cc

- From "Some Minesweeper Configurations",page 2

- From "Some Minesweeper Configurations",page 3

- From Richard Kaye: How Complicated is Minesweeper?, splitter (131072 solutions)

- From Richard Kaye: How Complicated is Minesweeper?, wire

- Problem 0 from Gecode minesweeper.cc
- send_more_money_any_base.co: SEND+MORE=MONEY in any base

- send_most_money.co: SEND+MOST=MONEY, where MONEY should be maximized

- seseman.co: simple recreational mathematics puzzle. See the CGI-program Seseman convent problem

- toNum.co: Demonstrates
`toNum`

for converting an array to number or vice versa

- xkcd.co: XKCD's knapsack problem. See the xkcd strip for the problem

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