Data sets
Multileaf Collimator Sequencing Problem
The benchmark used in [7,8] is avalaible here : irmt-instances.zip
It includes matrices ranging from 12 by 12 to 40 by 40 with maximum elements between 10 and 15.
Domino Portraits
The 0-9 grids used in [6] for Vermeer's "Girl with a Pearl Earring" are available here : grids.zip
The grids of ten additional pictures : grids10.zip
The pictures themselves : evalpics.zip
Timetabling (ITC 2007 : International Timetabling Competition)
A technical description of the problem used in the second Track of the competition on Course Timetabling can be found here : Post Enrolment based Course Timetabling. This problem comes from the problem used during the 2002 competition and has been enriched with hard constraints to increase the difficulty of finding feasible solution. The benchmark (format) is made of 24 instances (only 16 available for the moment) :
- The instances of 2007 : inst2007.zip
- The instances of 2002 : inst2002.zip
- Two sets of five instances used in a number of papers published on this problem : small.zip and medium.zip
Positive table constraints of large arity (configuration)
Some large arity tables coming from configuration benchmarks and used in my work on functional dependencies. The functional dependencies holding on those tables are included in the zip files.
- Two tables of the Renault configuration problem : RenaultR80R104.zip
- Two tables on configuration problems related to laptop and camera (unique identifiers havebeen removed from the original sets) : CameraLaptop.zip
- A table of Travel data : Travel.zip
Crossword Puzzles
Puzzles : puzzles.zip
- Herald Tribune Crosswords, Spring, 1999 used in [3,4]
- Puzzles used by Ginsberg in [1,2]
Dictionnaries : dict.zip
- UK : UK cryptic solvers dictionary (see UK.doc).
- words : The dictionary found in /usr/dict/words under Linux.
- test : Together with grid "05.01", this word list can be used to debug a model. There are 24 different solutions (48 if symmetric solutions are counted).
Kakuro puzzles
Three data sets generated by Helmut Simonis can be used as benchmark (kakuro tutorial) :
- Easy puzzles [.ecl]
- Medium puzzles [.ecl]
- Difficult puzzles [.ecl]
For some reasons, the files are in the format of Prolog facts. The task here is not to solve the problems which are very easy but to solve them without search, by propagation only.
References
[1] Ginsberg, M.L., "Dynamic Backtracking," Journal of Artificial Intelligence Researc (JAIR), Volume 1, pages 25-46, 1993.
[2] Ginsberg, M.L. et al., "Search Lessons Learned from Crossword Puzzles," AAAI-90, pages 210-215.
[3] X. Chen and P. Beek. Conflict-directed backjumping revisited. Journal of Artificial Intelligence Research, 14:53–81, 2001.
[4] G. Katsirelos and F. Bacchus. Generalized nogoods in CSPs. In National Conference on Artificial Intelligence (AAAI-2005), pages 390–396, 2005.
[5] H. Simonis. Kakuro as a Constraint Problem. Unpublished, 2007 (http://4c.ucc.ie/~hsimonis/kakuro.pdf)
[6] Hadrien Cambazard, John Horan, Eoin O'Mahony, and Barry O'Sullivan. Fast and Scalable Domino Portrait Generation. Proceedings of CP-AI-OR 2008.
[7] Hadrien Cambazard, Eoin O'Mahony, and Barry O'Sullivan. A Shortest Path-based Approach to the Multileaf Collimator Sequencing Problem. Proceedings of CP-AI-OR 2009.
[8] D. Baatar, N. Boland, S. Brand, and P.J Stuckey. Minimum cardinlaity matrix decomposition into consecutive ones matrices: CP and IP approaches. Proceedings of CPAIOR, pages 1-15, 2007.