Some declarative approaches in tackling hard combinatorial problems

       Agostino Dovier        Andrea Formisano        Enrico Pontelli


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.