×

zbMATH — the first resource for mathematics

Evaluating ASP and commercial solvers on the CSPLib. (English) Zbl 1179.90287
Summary: This paper deals with four solvers for combinatorial problems: the commercial state-of-the-art solver ILOG oplstudio, and the research answer set programming (ASP) systems dlv, smodels and cmodels. The first goal of this research is to evaluate the relative performance of such systems when used in a purely declarative way, using a reproducible and extensible experimental methodology. In particular, we consider a third-party problem library, i.e., the CSPLib, and uniform rules for modelling and instance selection. The second goal is to analyze the marginal effects of popular reformulation techniques on the various solving technologies. In particular, we consider structural symmetry breaking, the adoption of global constraints, and the addition of auxiliary predicates. Finally, we evaluate, on a subset of the problems, the impact of numbers and arithmetic constraints on the different solving technologies. Results show that there is not a single solver winning on all problems, and that reformulation is almost always beneficial: symmetry-breaking may be a good choice, but its complexity has to be carefully chosen, by taking into account also the particular solver used. Global constraints often, but not always, help opl, and the addition of auxiliary predicates is usually worth, especially when dealing with ASP solvers. Moreover, interesting synergies among the various modelling techniques exist.

MSC:
90C27 Combinatorial optimization
Software:
AMPL; ASSAT; Cmodels; CPLEX; CSPLib; Oz
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bosch, R., & Trick, M. (2002). Constraint programming and hybrid formulations for three life designs. In Proceedings of the fourth international workshop on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR 2002) (pp. 77–91). Le Croisic.
[2] Cadoli, M., & Mancini, T. (2006). Automated reformulation of specifications by safe delay of constraints. Artificial Intelligence, 170(8–9), 779–801. · Zbl 1131.68096 · doi:10.1016/j.artint.2006.01.008
[3] Cadoli, M., & Mancini, T. (2007). Using a theorem prover for reasoning on constraint problems. Applied Artificial Intelligence, 21(4/5), 383–404. · Zbl 1155.68506
[4] Cadoli, M., Mancini, T., Micaletto, D., & Patrizi, F. (2006). Evaluating ASP and commercial solvers on the CSPLib. In Proceedings of the seventeenth european conference on artificial intelligence (ECAI 2006) (pp. 68–72). IOS Press. · Zbl 1179.90287
[5] Cadoli, M., Mancini, T., & Patrizi, F. (2006). SAT as an effective solving technology for constraint problems. In Proceedings of the sixteenth international symposium on methodologies for intelligent systems (ISMIS 2006). Lecture Notes in Computer Science (Vol. 4203, pp. 540–549). Bari, Italy: Springer.
[6] Cadoli, M., & Schaerf, A. (2005). Compiling problem specifications into SAT. Artificial Intelligence, 162, 89–120. · Zbl 1132.68693 · doi:10.1016/j.artint.2004.01.006
[7] Castillo, E., Conejo, A. J., Pedregal, P., Garca, R., & Alguacil, N. (2001). Building and solving mathematical programming models in engineering and science. John Wiley & Sons. · Zbl 1029.90001
[8] Cheng, B. M. W., Choi, K. M. F., Lee, J. H.-M., & Wu, J.C.K. (1999). Increasing constraint propagation by redundant modeling: An experience report. Constraints, 4(2), 167–192. · Zbl 0949.68605 · doi:10.1023/A:1009894810205
[9] Crawford, J. M., Ginsberg, M. L., Luks, E. M., & Roy, A. (1996). Symmetry-breaking predicates for search problems. In Proceedings of the fifth international conference on the principles of knowledge representation and reasoning (KR’96) (pp. 148–159). Morgan Kaufmann.
[10] Dewdney, A. K. (1987). The game life aquires some successors in three dimensions. Science American, 224(2), 112–118. · doi:10.1038/scientificamerican0987-112
[11] Dovier, A., Formisano, A., & Pontelli, E. (2005). A comparison of CLP(FD) and ASP solutions to NP-complete problems. In Proceedings of the twentyfirst international conference on logic programming (ICLP 2005). Lecture Notes in Computer Science (Vol. 3668, pp. 67–82). Springer. · Zbl 1165.68486
[12] Ellman, T. (1993). Abstraction via approximate symmetry. In Proceedings of the thirteenth international joint conference on artificial intelligence (IJCAI’93) (pp. 916–921). Morgan Kaufmann.
[13] Fernández, A. J., & Hill, P. M. (2000). A comparative study of eight constraint programming languages over the Boolean and Finite Domains. Constraints, 5(3), 275–301. · Zbl 0954.68031 · doi:10.1023/A:1009816801567
[14] Finkel, R. A., Marek, V. W., & Truszczynski, M. (2004). Constraint Lingo: Towards high-level constraint programming. Software–Practice and Experience, 34(15), 1481–1504. · Zbl 02179498 · doi:10.1002/spe.623
[15] Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., et al. (2002). Breaking row and column symmetries in matrix models. In Proceedings of the eighth international conference on principles and practice of constraint programming (CP 2002). Lecture Notes in Computer Science (Vol. 2470, p. 462). Springer.
[16] Fourer, R., Gay, D. M., & Kernigham, B. W. (1993). AMPL: A modeling language for mathematical programming. International Thomson Publishing.
[17] Freuder, E. C., & Sabin, D. (1997). Interchangeability supports abstraction and reformulation for multi-dimensional constraint satisfaction. In Proceedings of the fourteenth national conference on artificial intelligence (AAAI’97) (pp. 191–196). AAAI Press/The MIT Press.
[18] Giunchiglia, F., & Walsh, T. (1992). A theory of abstraction. Artificial Intelligence, 57, 323–389. · Zbl 0762.68054 · doi:10.1016/0004-3702(92)90021-O
[19] Gu, J., Purdom, P., Franco, J., & Wah, B. (1997). Algorithms for the satisfiability (SAT) problem: A survey. In Satisfiability Problem: Theory and Applications, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (pp. 19–152). American Mathematical Society. · Zbl 0945.03040
[20] Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., et al. (2006). The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic, 7(3), 499–562. · Zbl 05456569 · doi:10.1145/1149114.1149117
[21] Lierler, Y., & Maratea, M. (2004). Cmodels-2: SAT-based Answer Set Solver enhanced to non-tight programs. In V. Lifschitz & I. Niemelä (Eds.), Proceedings of the seventh international conference on logic for programming and nonmonotonic reasoning (LPNMR 2004). Lecture Notes in Computer Science (Vol. 2923, pp. 346–350). Fort Lauderdale, FL, USA: Springer. · Zbl 1122.68377
[22] Lin, F., & Yuting, Z. (2004). ASSAT: Computing answer sets of a logic program by SAT solvers. Artificial Intelligence, 157(1–2), 115–137. · Zbl 1085.68544 · doi:10.1016/j.artint.2004.04.004
[23] Mancini, T., & Cadoli, M. (2005). Detecting and breaking symmetries by reasoning on problem specifications. In Proceedings of the sixth international symposium on abstraction, reformulation and approximation (SARA 2005). Lecture Notes in Artificial Intelligence (Vol. 3607, pp. 165–181). Springer.
[24] Mancini, T., & Cadoli, M. (2007). Exploiting functional dependencies in declarative problem specifications. Artificial Intelligence, 171, 985–1010. · Zbl 1168.68552 · doi:10.1016/j.artint.2007.04.017
[25] Neumaier, A., Shcherbina, O., Huyer, W., & Vinkó, T. (2005). A comparison of complete global optimization solvers. Mathematical Programming, 103(2), 335–356. · Zbl 1099.90001 · doi:10.1007/s10107-005-0585-4
[26] Niemelä, I. (1999). Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence, 25(3,4), 241–273. · Zbl 0940.68018 · doi:10.1023/A:1018930122475
[27] Pelov, N., De Mot, E., & Denecker, M. (2000). Logic Programming approaches for representing and solving Constraint Satisfaction Problems: A comparison. In M. Parigot & A. Voronkov (Eds.), Proceedings of the seventh international conference on logic for programming and automated reasoning (LPAR 2000). Lecture Notes in Computer Science (Vol. 1955, pp. 225–239). Springer. · Zbl 0988.68522
[28] Puget, J.-F. (1993). On the satisfiability of symmetrical constrained satisfaction problems. In H. J. Komorowski & Z. W. Ras (Eds.), Proceedings of the seventh international symposium on methodologies for intelligent systems (ISMIS’93). Lecture Notes in Computer Science (Vol. 689, pp. 350–361). Springer.
[29] Ramani, A., Aloul, F. A., Markov, I. L., & Sakallak, K. A. (2004). Breaking instance-independent symmetries in exact graph coloring. In Proceedings of design automation and test conference in europe (DATE 2004) (pp. 324–331). IEEE Computer Society Press.
[30] Régin, J.-C. (2003). Global constraints and filtering algorithms. In M. Milano (Ed.) Constraint and Integer Programming – Toward a Unified Methodology, Operations Research/Computer Science Interfaces, Vol. 27, chapter 4. Kluwer Academic Publisher.
[31] Shcherbina, O., Neumaier, A., Sam-Haroud, D., Vu, X.-H., & Nguyen, T.-V. (2003). Benchmarking global optimization and constraint satisfaction codes. In Proceedings of the first international workshop on global constraint optimization and constraint satisfaction (COCOS 2002). Lecture Notes in Computer Science (Vol. 2861, pp. 211–222). Springer. · Zbl 1296.90004
[32] Smith, B. M. (2002). A dual graph translation of a problem in ’life’. In Proceedings of the eighth international conference on principles and practice of constraint programming (CP 2002). Lecture Notes in Computer Science (Vol. 2470, pp. 402–414). Springer.
[33] Smith, B. M., Stergiou, K., & Walsh, T. (2000). Using auxiliary variables and implied constraints to model non-binary problems. In Proceedings of the seventeenth national conference on artificial intelligence (AAAI 2000) (pp. 182–187). AAAI Press/The MIT Press.
[34] Smolka, G. (1995). The Oz programming model. In Computer Science Today: Recent Trends and Developments. Lecture Notes in Computer Science (Vol. 1000, pp. 324–343). Springer.
[35] Ullman, J. D. (1988). Principles of database and knowledge base systems, Vol. 1. Computer Science Press.
[36] Van Hentenryck, P. (1999). The OPL optimization programming language. The MIT Press.
[37] Wallace, M., Schimpf, J., Shen, K., & Harvey, W. (2004). On benchmarking constraint logic programming platforms. Response to Fernández and Hill’s ”A comparative study of eight constraint programming languages over the Boolean and Finite Domains”. Constraints, 9(1), 5–34 · Zbl 1069.68034 · doi:10.1023/B:CONS.0000006181.40558.37
[38] Walsh, T. (2001). Permutation problems and channelling constraints. In R. Nieuwenhuis & A, Voronkov (Eds.), Proceedings of the eighth international conference on logic for programming and automated reasoning (LPAR 2001). Lecture Notes in Computer Science (Vol. 2250, pp. 377–391). Springer. · Zbl 1273.68365
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.