Data sets
Scheduling of observations on the VLT
Random instances used in [14]: astro.zip
Bin packing with linear usage costs
Random instances used in [13]: linearcost_binpack.zip
Euclidian P-median
Irish and UK instances used in [12]:
Traveling Purchaser Problem
The problems of class 3 used by [10, 11] : tppbench.zip
Bin Packing
The falkenauer benchmark as well as the B1, B2, B3 instances are available here : bin-packing.zip
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.
The benchmark used in [9] is available here : imrt-large-real-instance.zip
It includes matrices ranging from 12 by 12 to 80 by 80 with maximum elements between 10 and 25. It also includes a set of clinical instances.
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.
[9] Hadrien Cambazard, Eoin O'Mahony, and Barry O'Sullivan. Hybrids Methods for the Multileaf Collimator Sequencing Problem. Proceedings of CP-AI-OR 2010.
[10] Gilbert Laporte, Jorge Riera-Ledesma, Juan José Salazar Gouzalez: A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem.Operations Research 51 (6): 940-951 (2003)
[11] Hadrien Cambazard, Bernard Penz: A Constraint Programming Approach for the Traveling Purchaser Problem. CP 2012: 735-749
[12] Hadrien Cambazard, Deepak Mehta, Barry O'Sullivan, Luis Quesada: A Computational Geometry-Based Local Search Algorithm for Planar Location Problems. CPAIOR 2012: 97-112
[13] Hadrien Cambazard, Deepak Mehta, Barry O'Sullivan, Helmut Simonis: Bin Packing with Linear Usage Costs - An application to Energy Management in Data Centres. Proceedings of CP 2013: 47-62
[14] Nicolas Catusse, Hadrien Cambazard, Nadia Brauner, Pierre Lemaire and Bernard Penz: A Branch and Price Algorithm for Scheduling Observations on a Telescope. IJCAI 2016