Promoting robust black-box solvers through competitions. (English) Zbl 1208.68203
Summary: This paper presents the experiences of the organizers of the four constraint solver competitions which were held in conjunction with CP in the previous years. The paper mainly focuses on the competitions which were held in 2008 and 2009, outlines the reasons for organizing the competitions, describes how the solvers were evaluated, and presents lessons, observations, and general trends.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
References:
| [1] | Baptista, L., Lynce, I., & Marques-Silva, J. P. (2001). Complete search restart strategies for satisfiability. In Proceedings of SSA’01 workshop held with IJCAI’01. · Zbl 1053.68684 |
| [2] | Boussemart, F., Hemery, F., Lecoutre, C., & Sais, L. (2004). Boosting systematic search by weighting constraints. In Proceedings of ECAI’04 (pp. 146–150). |
| [3] | Carlsson, M. (2006). Filtering for the case constraint. Talk given at the School on Global Constraints. |
| [4] | Cheng, K., & Yap, R. (2008). Maintaining generalized arc consistency on ad-hoc r-ary constraints. In Proceedings of CP’08 (pp. 509–523). |
| [5] | Cheng, K., & Yap, R. (2008). An overview of mddc-solve. In M. R. C. van Dongen, C. Lecoutre, & O. Roussel (Eds.), Proceedings of the third constraint solver competition (pp. 3–7). |
| [6] | Correia, M., & Barahona, P. (2008). Overview of the CaSPER constraint solvers. In M. R. C. van Dongen, C. Lecoutre, & O. Roussel (Eds.), Proceedings of the third constraint solver competition (pp. 15–24). |
| [7] | Fukunaga, A. S. (2003). Complete restart strategies using a compact representation of the explored search space. In Proceedings of SSA’03 workshop held with IJCAI’03. |
| [8] | Geelen, P. A. (1992). Dual viewpoint heuristics for binary constraint satisfaction problems. In Proceedings of ECAI’92 (pp. 31–35). |
| [9] | Gent, I. P., Jefferson, C., & Miguel, I. (2006). Minion: A fast, scalable constraint solver. In Proceedings of ECAI’06 (pp. 98–102). |
| [10] | Gomes, C., Selman, B., Crato, N., & Kautz, H. (2000). Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning, 24, 67–100. · Zbl 0967.68145 · doi:10.1023/A:1006314320276 |
| [11] | Grimes, D. (2008). A comparison of boosted versus unboosted weighted degree search. In M. R. C. van Dongen, C. Lecoutre, & O. Roussel (Eds.), Proceedings of the third constraint solver competition (pp. 25–30). |
| [12] | Haralick, R. M., & Elliott, G. L. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14, 263–313. · doi:10.1016/0004-3702(80)90051-X |
| [13] | Hebrard, E. (2008). Mistral, a constraint satisfaction library. In M. R. C. van Dongen, C. Lecoutre, & O. Roussel (Eds.), Proceedings of the third constraint solver competition (pp. 31–39). |
| [14] | Hebrard, E. (2008). Implementing a constraint solver: A case study. In Slides of the workshop of the third international constraint solver competition. http://www.cril.univ-artois.fr/CPAI08 . |
| [15] | Lecoutre, C. (2008). Optimization of simple tabular reduction for table constraints. In Proceedings of CP’08 (pp. 128–143). |
| [16] | Lecoutre, C., Sais, L., Tabary, S., & Vidal, V. (2007). Recording and minimizing nogoods from restarts. Journal on Satisfiability, Boolean Modeling and Computation (JSAT), 1, 147–167. · Zbl 1144.68373 |
| [17] | O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., & O’Sullivan, B. (2008). Using case-based reasoning in an algorithm portfolio for constraint solving. In M. R. C. van Dongen, C. Lecoutre, & O. Roussel (Eds.), Proceedings of the third constraint solver competition (pp. 53–62). |
| [18] | Prosser, P., Stergiou, K., & Walsh, T. (2002). Singleton consistencies. In Proceedings of CP’00 (pp. 353–368). · Zbl 1044.68790 |
| [19] | Puget, J. F. (2004). Constraint programming next challenge: Simplicity of use. In Proceedings of CP’04 (pp. 5–8). Invited talk. |
| [20] | Refalo, P. (2004). Impact-based search strategies for constraint programming. In Proceedings of CP’04 (pp. 557–571). · Zbl 1152.68577 |
| [21] | Roussel, O., & Lecoutre, C. (2009). XML representation of constraint networks: Format XCSP 2.1. Technical report. arXiv:0902.2362 . CoRR. |
| [22] | Sanchez, M., Bouveret, S., de Givry, S., Heras, F., Jegou, P., Larrosa, J., et al. (2008). Max-CSP competition 2008: Toulbar2 solver description. In M. R. C. van Dongen, C. Lecoutre, & O. Roussel (Eds.), Proceedings of the third constraint solver competition (pp. 63–70). |
| [23] | Tamura, N., Taga, A., Kitagawa, S., & Banbara, M. (2006). Compiling finite linear CSP into SAT. In Proceedings of CP’06 (pp. 590–603). · Zbl 1160.68567 |
| [24] | Tamura, N., Tanjo, T., & Banbara, M. (2008). System description of a SAT-based CSP solver: Sugar. In M. R. C. van Dongen, C. Lecoutre, & O. Roussel (Eds.), Proceedings of the third constraint solver competition (pp. 71–75). |
| [25] | The Choco Team. Choco: An open source Java constraint programming library. In M. R. C. van Dongen, C. Lecoutre, & O. Roussel (Eds.), Proceedings of the third constraint solver competition (pp. 8–14). |
| [26] | Ullmann, J. R. (2007). Partition search for non-binary constraint satisfaction. Information Science, 177, 3639–3678. · Zbl 1119.68446 · doi:10.1016/j.ins.2007.03.030 |
| [27] | van Dongen, M. R. C. (2006). Beyond singleton arc consistency. In Proceedings of ECAI’06 (pp. 163–167). |
| [28] | van Dongen, M. R. C., Lecoutre, C., & Roussel, O. (Eds.) (2008). Proceedings of the third constraint solver competition. http://www.cril.univ-artois.fr/CPAI08/Competition-08.pdf . |
| [29] | Zhou, N.-F. (2008). bp-solver 2008. In M. R. C. van Dongen, C. Lecoutre, & O. Roussel (Eds.), Proceedings of the third constraint solver competition (pp. 83–90). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
