My Constraint Programming Blog

During the week some more Comet models has been published. Many of them are translations of my MiniZinc models.

Findings this week

Here are some findings for the previous week.

tryall again: Nonogram

One of the models I really wanted to make was Nonogram, since it would be interesting to compare with the MiniZinc model nonogram.mzn and the Gecode/R model nonogram.rb. The Comet model is nonogram.co.

The first version was very influenced by the MiniZinc model, and used tryall where the MiniZinc model used exists (see the previous post About 20 more constraint programming models in Comet for some more comments ablit this). But this was way too slow.

After some thoughts, I rewrote the tryall:s and it was getting faster. For a simple Nonogram problem like The Hen (see picture below), it originally took about 30 seconds. And after the changes, it now takes a fraction of a second (with alot of fewer propagations).

Nonogram The hen
. X X X . . . .
X X . X . . . .
. X X X . . X X
. . X X . . X X
. . X X X X X X
X . X X X X X .
X X X X X X . .
. . . . X . . .
. . . X X . . .


Still, compared to the Gecode/R (and - of course - Gecode) models, which uses "regular expression" representation, the Comet model is slow, but is faster the MiniZinc version. For example the Lambda picture (see below) takes about 12 seconds with the Comet model, compared to 0.5 seconds with the Gecode/R model. Well, it is nice to have some more optimization to do (or more probably, a complete remodelling)...

Nonogram: Lambda problem
. X X . . . . . . .
X . X X . . . . . .
X . . X . . . . . .
. . . X X . . . . .
. . . . X . . . . .
. . . X X X . . . .
. . . X X X . . . .
. . X X . X X . . .
. . X X . . X . . .
. X X . . . X X . X
. X X . . . . X X X
X X . . . . . X X .


To summarize, the main finding here was to replace two tryall statements with two decision variables, and change the rest accordingly. The model also include two symmetry breaking constraints ("alldifferent except 0" and ordering of a temporary array), but these make no big difference.

binary representation of set variables

As far as I know, Comet don't (yet) have a variable set variables (i.e. as decision variables). Instead, another representation must be used, and probably the most natural representation is an array of binary decision values representing each value of the set.

The following models use this representation:
* set_partition.co, partitions a range of integers 1..n in two equal sized sets where the sums and sums of squares of the two sets are equal.
* steiner_triplets.co: the well known problem of Steiner triples.
* partition_function.co, (partitions values according to a function of some kind)

Models

These models is available by My Comet page. As usual, the problems are presented in the header of the file.

• 3_jugs.co: 3 jugs problem, water bucket problem (as shortest path problem). Compare with water_buckets1.co below.
• all_interval.co: All interval problem (series), (CSPLib problem 7)
• extensional_support.co: Global constraint extensional support/conflict (a.k.a. in_relation, forbidden/allowed assignments etc)
• isbn.co: Some explorations of ISBN13
• maximum_density_still_life_cp.co: Maximum density still life (CP model)
• nonogram.co: Nonogram (paint by numbers).
  Data files for the Nonogram model. To use these files, add an include "filename" in the model file.
  • nonogram_car.co: Car
  • nonogram_dragonfly.co: Dragonfly
  • nonogram_hard.co: "Hard" (I don't know where I got this problem, but it is not very hard).
  • nonogram_hen.co: Hen
  • nonogram_lambda.co: Lambda
  • nonogram_n4.co: Problem N4 from the ECLiPSe Nonogram program nono.ecl.
  • nonogram_n6.co: Problem N6
  • nonogram_nonunique.co: Nonunique problem
• partition_function.co: Partitions a set of integers (represented as a boolean matrix) according to a function.
• rot13.co: Some explorations of ISBN13
• runs.co: Number of runs in a sequence
• sat.co: Satisfiability Problem (from GLPK's example)
• set_covering2.co: Set covering: security telephone on campus (Taha "Operations Research", example 9.1-2)
• set_covering3.co: Set covering: assigning senators to committees (Murty "Optimization Models for Decision Making")
• set_covering4.co: Set covering/partition problem (Lundgren, Rönnqvist, Värbrand "Optimeringslära", page 408)
• set_covering5.co: Set covering, work scheduling (Lundgren, Rönnqvist, Värbrand "Optimeringslära", page 410)
• set_covering_skiena.co: Set covering (Skiena)
• set_partition.co: Set partition problem (using boolean matrix as representation of the sets)
• spreadsheet.co: Simple "spreadsheet" example (Apt)
• steiner_triplets.co: Steiner triplets (using arrays of booleans to represent the sets)
• temporal_reasoning.co: Temporal reasoning (Apt)
• water_buckets1.co: 3 jugs problem, water bucket problem (as shortest path problem). Compare with 3_jugs_co above.
• word_design_dna1.co: Word design for DNA computing on surfaces (CSPLib 033)