An empirical study of constraint logic programming and answer set programming solutions of combinatorial problems. (English) Zbl 1193.68073
Summary: This paper presents experimental comparisons between the declarative encodings of various computationally hard problems in Answer Set Programming (ASP) and Constraint Logic Programming over Finite Domains (CLP(FD)). The objective is to investigate how solvers in the two domains respond to different problems, highlighting the strengths and weaknesses of their implementations, and suggesting criteria for choosing one approach over the other. Ultimately, the work in this paper is expected to lay the foundations for a transfer of technology between the two domains, for example by suggesting ways to use CLP(FD) in the execution of ASP.
References:
| [1] | Anger C, ALP Newsletter 17 (2004) |
| [2] | DOI: 10.1017/CBO9780511543357 · doi:10.1017/CBO9780511543357 |
| [3] | Clote P, Computational Molecular Biology (2001) |
| [4] | DOI: 10.1089/cmb.1998.5.423 · doi:10.1089/cmb.1998.5.423 |
| [5] | DOI: 10.1186/1471-2105-5-186 · doi:10.1186/1471-2105-5-186 |
| [6] | DOI: 10.1145/368273.368557 · Zbl 0217.54002 · doi:10.1145/368273.368557 |
| [7] | DOI: 10.1145/321033.321034 · Zbl 0212.34203 · doi:10.1145/321033.321034 |
| [8] | Diaz D, Journal of Functional and Logic Programming 6 (2001) |
| [9] | Dovier, A, Formisano, A and Pontelli, E. 2005. ”A Comparison of CLP(FD) and ASP in Tackling Hard Combinatorial Problems”. www.di.univaq.it/ formisano/CLPASP · Zbl 1165.68486 |
| [10] | Elkabani, I, Pontelli, E and Son, TC. 2004. Smodels with CLP and its Applications: A Simple and Effective Approach to Aggregates in ASP. Proceedings of ICLP04. 2004. pp.73–89. · Zbl 1104.68375 |
| [11] | Elkhatib, O, Pontelli, E and Son, TC. 2004. A Tool for Reasoning About Answer Sets in Prolog. Proceedings of PADL. 2004. pp.148–162. |
| [12] | Erdem E, TPLP 3 pp 499– (2004) |
| [13] | DOI: 10.1023/A:1009816801567 · Zbl 0954.68031 · doi:10.1023/A:1009816801567 |
| [14] | DOI: 10.1007/3-540-45632-5_16 · doi:10.1007/3-540-45632-5_16 |
| [15] | Gelfond, M and Lifschitz, V. 1988. The Stable Model Semantics for Logic Programming. Proceedings of ICLP88. 1988. pp.1070–1080. Boston, MA: MIT Press. |
| [16] | Gelfond M, Electronic Transactions on Artificial Intelligence 2 pp 193– (1998) |
| [17] | Giunchiglia, E, Lierler, Y and Maratea, M. SAT-based Answer Set Programming. Proceedings of AAAI’04. 2004. pp.61–66. · Zbl 1107.68029 |
| [18] | DOI: 10.1007/s10817-006-9033-2 · Zbl 1107.68029 · doi:10.1007/s10817-006-9033-2 |
| [19] | DOI: 10.1016/0743-1066(94)90033-7 · doi:10.1016/0743-1066(94)90033-7 |
| [20] | Lee, J and Lifschitz, V. 2003. Loop Formulas for Disjunctive Logic Programs. Proceedings of ICLP03. 2003. pp.451–465. · Zbl 1204.68056 |
| [21] | Lierler, Y and Maratea, M. 2004. CMODELS-2: SAT-based Answer Set Solver Enhanced to Non-tight Programs. Proceedings of LPNMR04. 2004. pp.346–350. · Zbl 1122.68377 |
| [22] | Lifschitz, V. 1999. Answer Set Planning. Proceedings of ICLP99. 1999. pp.23–37. |
| [23] | DOI: 10.1145/1131313.1131316 · Zbl 1367.68036 · doi:10.1145/1131313.1131316 |
| [24] | Lin, F and Zhao, Y. ASSAT: Computing Answer Sets of a Logic Program by SAT Solvers. Proceedings of AAAI’02. 2004. pp.112–117. · Zbl 1085.68544 |
| [25] | DOI: 10.1145/116825.116836 · Zbl 0799.68176 · doi:10.1145/116825.116836 |
| [26] | Marek, VW and Truszczyński, M. 1999. Stable Models and an Alternative Logic Programming Paradigm. The Logic Programming Paradigm. 1999, Berlin. pp.375–398. Springer Verlag. · Zbl 0979.68524 |
| [27] | Marriott K, Programming with Constraints (1998) |
| [28] | Moskewicz, MW, Madigan, CF, Zhao, Y, Zhang, L and Malik, S. 2001. Chaff: Engineering an Efficient SAT Solver. Proceedings of Design Automation Conference. 2001. pp.530–535. |
| [29] | Papadimitriou CH, Computational Complexity (1994) |
| [30] | Prestwich, SD. 2003. Local Search on SAT-encoded Colouring Problems. Proceedings of SAT 2003, 6th International Conference. 2003. pp.105–119. · Zbl 1204.68208 |
| [31] | Simons P, Doctoral dissertation (2000) |
| [32] | Son, TC, Baral, C and McIlraith, S. 2003. Planning with Different Forms of Domain-dependent Control Knowledge – An Answer Set Programming Approach. Proceedings of LPNMR01. 2003. pp.226–239. · Zbl 1007.68591 |
| [33] | Thielscher, M. 2002. Reasoning about Actions with CHRs and Finite Domain Constraints. Proceedings of ICLP02. 2002. pp.70–84. · Zbl 1045.68039 |
| [34] | DOI: 10.1023/B:CONS.0000006181.40558.37 · Zbl 1069.68034 · doi:10.1023/B:CONS.0000006181.40558.37 |
| [35] | Weisstein, EW. 2005. ”Schur Number”. mathworld.wolfram.com/SchurNumber.html |
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.
