ASP Benchmark: Randomly Generated Logic Programs



Benchmarks:

RLP (Randomly generated Logic Programs) can be used as benchmark problems for ASP (Answer Set Programming) systems. For more details of the research of RLP under answer set semantics please refer to this paper.

It is observed that there is an "easy-hard-easy" pattern in k-LP(N). For 3-LP(N), the hard-job region is around L/N= 5, where L is the number of rules and N the number of atoms. Here we have collected some logic programs in the hard-job region in 3-LP(150) and 3-LP(200), from L/N = 3 to 8 with a step of 0.5, and put forward as benchmarks for ASP. More specifically, in 3-LP(150, L) and 3-LP(200, L), we have collected the top 10 hard programs for ASSAT, DLV, and Smodels respectively, in a sample of the size 1000. So we have 30 programs in each class, but several are duplicate.




Experimental Results:

In the following tables, we give out the statistics of the experimental results of ASSAT 1.5, DLV (April 12th, 2002 version), and Smodels 2.27 on these programs. The experiments were done on Sun Ultra 5 machines with a 400 MHz UltraSPARC-IIi CPU and 256M memory running solaris. The reported times are in CPU seconds as reported by Unix ``time'' command.

Benchmark: 3-LP(150)

L/N Number of ASSAT ' DLV ' Smodels '
' instance Mean STDEV Mean STDEV Mean STDEV
3 25 2.07 0.50 14.50 7.78 2.57 1.23
3.5 23 4.23 1.92 41.16 25.98 7.44 3.19
4 24 6.67 2.72 96.35 40.51 17.61 7.58
4.5 26 9.79 5.42 137.95 68.18 34.87 26.85
5 27 8.37 4.41 107.71 44.50 33.44 19.74
5.5 25 12.01 9.02 77.49 43.05 29.19 19.30
6 28 5.98 2.78 43.23 23.20 14.02 6.66
6.5 29 5.70 4.15 24.33 12.38 10.73 5.11
7 27 4.61 2.93 13.84 6.05 6.59 2.77
7.5 29 3.19 1.60 7.89 4.29 3.69 1.33
8 29 2.75 1.18 5.53 2.25 3.02 0.75







Benchmark: 3-LP(200)

L/N Number of ASSAT ' DLV ' Smodels '
' instance Mean STDEV Mean STDEV Mean STDEV
3 25 6.03 3.45 171.68 83.82 10.75 7.60
3.5 24 33.83 19.70 1458.88 849.44 118.83 76.91
4 24 88.57 61.27 3086.86 1760.69 427.98 313.58
4.5 23 136.07 111.00 3682.77 2117.81 1077.74 829.07
5 27 143.67 91.78 2810.51 1582.58 869.24 518.66
5.5 26 105.78 66.81 2129.02 1390.93 689.40 403.59
6 26 62.77 45.56 918.61 377.14 394.28 270.24
6.5 24 44.15 27.73 358.50 176.64 187.29 119.14
7 27 20.80 11.84 144.63 75.18 85.48 60.08
7.5 28 17.89 14.64 73.14 37.28 38.08 20.14
8 28 8.56 7.09 40.66 22.97 19.37 7.98







More Randomly Generated Logic Programs:

We also prepare more randomly generated logic programs for interested researchers. Here we provide 3000 instances in 3-LP(150, L) and 3-LP(200, L), for L/N = 0.5 to 12.








References:

Yuting Zhao and Fangzhen Lin, Answer Set Programming Phase Transition: A study on Randomly Generated Programs, In Proceedings the Nineteenth International Conference on Logic Programming (ICLP'03), 2003. To appear.

Yuting Zhao
Last modified: Oct 2003