My Constraint Programming Blog

Since Some Comet constraint programming (CP) models, I've continued to translate some more of my (approx. 600) MiniZinc models to Comet. There are a few new models: game_theory_taha.co and fill_in_the_squares.co.

Findings this week

tryall

One finding this week is that tryall almost behaves like MiniZinc's exists, a very useful modelling tool. See for example the following models for the usage:
* Hidato puzzle
* Knights path
* SONET problem
* Word golf.

tryall behaves slightly different depending where it is placed: In the main explore/exploreall section, it may not generate all the solutions; but when placed in the using section, it generates all the solutions (and makes the model a bit slower).

Search strategies (labelling)

I've started to experiment with different search strategies (labelling), but for most of the models, the two builtin label and labelFF (first fail) are reasonable fast. This is an area I will look into more.

Other things

* strings/dictionaries: It is very nice to be able to use "real" strings in modelling. See for example Word golf, and Set covering deployment. The latter model also - just for fun - has a hash table for counting the number of occurrences of the selected countries.

* more than one models in the same program. MiniZinc only allows one model per file. As an experiment, game_theory_taha.co (two player zero sum game) solves first for one player, and then another model for the second player (which is not necessary since the solutions are a dual problem). Also, in Word golf, there is a loop of models solving for different ladder lengths.

The models

As usual, the description of the problem is included in the model, and a reference to my other model(s) of the same problem.

bus_schedule.co: Bus scheduling (Taha)
calculs_d_enfer.co: Calculs d'enfer puzzle (from the NCL manual)
crew.co: Crew scheduling (Gecode)
discrete_tomography.co: Discrete Tomography (one color model)
fill_in_the_squares.co: Fill in the squares, recreational mathematics. (from ZDC system). Origin unknown.
furniture_moving.co: Optimizing furniture moving (Marriott and Stuckey)
game_theory_taha.co: 2 player zero sum game (Taha). This uses the MIP (mixed integer programming) module.
heterosquare_cp.co: Heterosquare problem
hidato.co: Hidato puzzle
knights_path.co: Knight path
least_square.co: Least square (From Lundgren, Rönnqvist, Värbrand: "Optimeringslära"), using the MIP module.
max_flow_winston1.co: Maximum flow problem (Winston)
pandigital_numbers.co: Pandigital numbers (any base << about 12)
photo_problem.co: Photo problem
place_number_puzzle.co: Eight number placement puzzle
quasigroup_completion.co: Quasigroup completion problem.
Problem files:

• quasigroup1.txt
  
• quasigroup2.txt
  
• quasigroup3.txt
  
• quasigroup4.txt
  
• quasigroup5.txt
  
• quasigroup6.txt
  
• quasigroup7.txt
  
• quasigroup8.txt
  
• quasigroup9.txt

set_covering.co: Set covering, placing of firestations (Winston)
set_covering_deployment.co: Set covering deployment
sonet_problem.co: SONET problem
survo_puzzle.co: Survo puzzle
traffic_lights.co:Traffic lights problem (CSPLib problem 16)
who_killed_agatha.co: Who killed agatha? (The Dreadsbury Mansion Murder Mystery, a automated reasoning problem)
word_golf.co: Word golf (word chain, word ladder), word_golf_len3.co: Data file with 2044 3-letter words.
young_tableaux.co: Young tableaux and partitions