A comparison of Constraint Logic Programming over Finite Domains and Answer Set Programming in tackling hard combinatorial problems

Agostino Dovier
Università di Udine,
DMIF
Home page
Andrea Formisano
Università di Udine,
DMIF
Home page
Enrico Pontelli
New Mexico State University,
Department of Computer Science
Home page

Abstract:

In these pages we present experimental comparisons between declarative encodings of various computationally hard problems in both Answer Set Programming (ASP) and Constraint Logic Programming (CLP) over finite domains. The objective is to identify how the solvers in the two domains respond to different problems, highlighting strengths and weaknesses of their implementations and suggesting criteria for choosing one approach versus the other. Ultimately, the work in this research is expected to lay the ground for transfer of concepts between the two domains.

The CLP programs have been designed for execution by SICStus Prolog 3.11.2 (using the library clpfd)--though the code is general enough to be used on different platforms with little syntactic adjustment (in some cases, we provide the code usable with BProlog or GNU-Prolog).

The ASP programs have been designed to be grounded by lparse and processed by smodels (version 2.28) or cmodels (version 3.03). The CModels system makes use of a SAT solver to compute answer sets--we run all experiments using the default SAT solver, namely mChaff. In some cases we also report the results obtained using Simo, Relsat, or zChaff.

All timings are in seconds.

Part of the material in this web site originated the paper: A Comparison of CLP(FD) and ASP Solutions to NP-Complete Problems. ICLP 2005, pp.67-82, Lecture Notes in Computer Science, vol.3668.