Experiments/Benchmarks

We have experimented cloopD on Niemelä's encoding of the Hamiltonian circuit problem and DLV's encoding of the Hamiltonian circuit problem, and consider graphs with the special structure. Specifically, we create some copies of a complete graph, and then randomly add some arcs to connect these copies into a strongly connected graph such that Hamiltonian circuit for this graph must go through these special arcs. The problems are first grounded by gringo (version 3.0.1, The result is similar when programs are grounded by Lparse (version 1.1.2)), then computed by different ASP solvers. For these programs, information from cloopD makes clasp (version 1.3.4), claspD (version 1.1) and cmodels (version 3.79) run much faster when looking for an answer set, as demonstrated in Table 1 and 2.

Our experiments were done on a 4XAMD Opteron 844 (1.8GHz) CPU and 8GB RAM. The reported times are in CPU seconds as reported by Linux "/usr/bin/time" command.

In Table 1 and 2,   NxM stands for a graph with M copies of the complete graph with N nodes: C₁, ..., C_M,  and with exactly one arc from C_i to C_i+1,   for each 1≤i≤M ( C_M+1 is defined to be C₁ ).  We randomly created 20 different graphs for each NxM, and the times reported in the table refers the average times for these corresponding 20 problems. ">2h" indicates the run didn't return in two hour, "cmodels with cloopD", "clasp with cloopD", and "claspD with cloopD" stand for the running time for cmodels, clasp, and claspD after adding constraints returned from cloopD to the program. Note that,  cloopD returns literals that can be computed by an iterative procedure based on unit propagation from the program completion and the loop formulas of loops with at most one external support rule, i.e. the function T₁(P) in the paper. Thus "cmodels with cloopD", "clasp with cloopD", and "claspD with cloopD" used here refer to "comdels_T1", "clasp_T1", and "claspD_T1".

Table 1: Run-time Data for Normal Logic Programs.

                                                                             *The program does not terminate in 2 hours for some instances, we count their time as 2 hours.