Next: Discussion Up: Results of Experiments Previous: Comparison with Evolutionary Algorithms


Comparison with Local Search Algorithms

We consider two local search techniques, GRASP [11] and GSAT [12], which are amongst the best local search algorithms for SAT. GRASP (Greedy Randomized Search Procedure) is a general search technique: a potential solution is constructed according to a suitable greedy heuristic, and improved by a local search procedure. These two steps are repeated until either an optimal solution is found or a maximum number of iterations has been reached. In (the extended version of) [11] four GRASP algorithms for SAT are introduced. GSAT is a greedy heuristic: one starts from a randomly generated candidate solution and iteratively tries to increase the number of satisfied clauses by flipping the value of a suitable variable. The variable chosen for flipping is the one that gives the highest increase in the number of satisfied clauses.

We compare these two algorithms with ASAP on a subset of DIMACS instances reported in the extended version of [11]. All the considered instances are satisfiable. These instances for SAT stem from different sources and are grouped into families.

- The aim family contains artificially generated 3-SAT instances and are constructed to have exactly one solution. The number of variables is 50, 100 and 200 and the ratio n_clauses/n_vars is 2.0, 3.4 and 6.0. In total there are 36 instances.

- Family par instances arise from a problem in learning the parity function. These are 5 instances with a varying number of variables and clauses.

- The 16 Jnh instances are randomly generated and have a varying clause length.

- Instances ii arise from the ``boolean function synthesis'' problem; they have a number of variables ranging from 66 to 1728 and number of clauses ranging from few hundreds up to over 20 thousands. This family counts 41 instances.

Execution time is the performance measure used in the DIMACS Challenge to evaluate local search algorithms. Our code was written in C and ran on Intel Pentium II (Memory: 64 Mb ram, Clock: 350 MHz, Linux version: Red Hat 5.2). In order to compare ASAP with GRASP and GSAT, we report in Table 11 the results of the DIMACS Challenge machine benchmark on the Pentium II and on the SGI Challenge, the machine used in the experiments with GRASP and GSAT reported in (the extended version of) [11]. The results indicate that the Pentium II is approximately 1.5 times faster than the SGI Challenge.

The results of the experiments are given in Tables 3-10. Again, n and m denote the number of variables and of clauses, respectively. All the algorithms are run 10 times on each instance. In the tables containing the results of ASAP we give the average number of iterations, of restarts, of accepted flips, and the average time (in seconds) together with the standard deviation. In the Tables comparing ASAP with GRASP and GSAT we give the average time of ASAP (run on Pentium II), and report the results contained in (the extended version of) [11] (run on SGI Challenge), where an entry labeled `-' means that the result for that instance has not been given in [11].

All algorithms were always able to find the solution on every instance, except on the instances relative to the entries labeled `NF' (not found) where ASAP was not able to find a solution.

The results of the tables comparing ASAP with GRASP and GSAT show that ASAP is competitive with these two algorithms, except on the instance aim-100-2_0-yes1 and on those of the class par16-c, where ASAP is not able to find any solution within 300000 chromosome evaluations.

On the other instances, we can summarize the results as follows. The performance of ASAP on the class aim is rather satisfactory, finding the solution in much shorter time than GRASP on some instances, like aim-200-6_0-yes1. On the class par8 ASAP outperforms GSAT and has performance comparable to the one of GRASP. However, on the class par16 ASAP is not able to find any solution. On the class Jnh GSAT outperforms GRASP as well as ASAP, with ASAP and GRASP giving comparable results. Finally, on class ii ASAP outperforms GRASP and GSAT on instances ii8 and ii16 (except ii16e1 where GSAT is faster), while GSAT outperforms GRASP and ASAP on instances ii32, being ASAP on the average faster than GRASP.


Table 3: Results of ASAP on class aim
          Accepted Time
Inst. n m Iterations Restarts Flips avg SDev
aim-50-2_0-yes1 50 100 28112 349 1693310 18.758 22.744
aim-50-3_4-yes1 50 170 42 1 1979 0.050 0.073
aim-50-6_0-yes1 50 300 3 0 143 0.006 0.008
aim-100-3_4-yes1 100 340 115 6 11672 0.329 0.420
aim-100-6_0-yes1 100 600 4 0 386 0.022 0.017
aim-200-3_4-yes1 200 680 2774 208 614675 20.70 28.348
aim-200-6_0-yes1 200 1200 6 0 1376 0.110 0.089


Table 4: Comparison of ASAP, GRASP and GSAT on class aim
Inst. ASAP GRASP-A GRASP-B GRASP-C GRASP-D GSAT
aim-50-2_0-yes1 18.76 2.23 4.86 2.27 2.14 3.33
aim-50-3_4-yes1 0.05 0.60 1.01 0.59 0.36 0.10
aim-50-6_0-yes1 0.01 0.08 0.07 0.08 0.05 0.03
aim-100-2_0-yes1 NF 543.51 1386.51 2048.52 836.12 5883.12
aim-100-3_4-yes1 0.33 30.94 54.71 46.71 34.00 0.85
aim-100-6_0-yes1 0.02 0.66 0.71 0.72 0.63 0.35
aim-200-3_4-yes1 20.70 - - - - -
aim-200-6_0-yes1 0.11 126.99 121.90 176.91 120.04 -


Table 5: Results of ASAP on class par
          Accepted Time
Inst. n m Iters Rest. Flips avg SDev
par8-1-c 64 254 149 9 8418 0.26 0.41
par8-2-c 68 260 121 6 7374 0.23 0.16
par8-3-c 75 298 281 14 18487 0.58 0.54
par8-4-c 67 266 469 19 23015 0.80 0.49
par8-5-c 75 298 674 46 45501 1.43 1.16


Table 6: Comparison of ASAP, GRASP and GSAT on class par
Inst. ASAP GRASP-A GRASP-B GRASP-C GRASP-D GSAT
par8-c 0.65 0.16 0.17 3.62 2.80 99.37
par16-c NF 1981.13 3541.71 5205.23 3408.44 25273.14


Table 7: Results of ASAP on class Jnh
          Accepted Time
Inst. n m Iterations Restarts Flips avg SDev
jnh1 100 850 852 34 83459 16.32 13.28
jnh7 100 850 21 1 2351 0.43 0.16
jnh12 100 850 129 71 12669 2.57 2.45
jnh17 100 850 837 3 8477 1.67 1.40
jnh201 100 800 21 0 2458 0.42 0.34
jnh204 100 800 368 18 36046 6.49 4.01
jnh205 100 800 203 6 20037 3.59 2.20
jnh207 100 800 1529 97 151247 26.63 24.36
jnh209 100 800 359 22 35115 6.22 5.15
jnh210 100 800 21 1 2288 0.39 0.28
jnh212 100 800 4430 273 429970 78.00 85.15
jnh213 100 800 49 2 4890 0.85 0.97
jnh217 100 800 30 1 3219 0.56 0.35
jnh218 100 800 35 1 3820 0.66 0.65
jnh220 100 800 1644 105 162005 28.85 24.93
jnh301 100 900 1232 81 115059 25.58 16.65


Table 8: Comparison of ASAP, GRASP and GSAT on class Jhn
Inst. ASAP GRASP-A GRASP-B GRASP-C GRASP-D GSAT
jnh1 16.32 11.87 5.19 10.14 8.11 0.71
jnh7 0.43 3.61 1.76 2.07 1.09 0.07
jnh12 2.51 0.84 1.36 1.24 1.95 0.74
jnh17 1.67 1.66 2.00 3.52 2.89 0.19
jnh201 0.42 1.48 0.50 0.73 0.74 0.05
jnh204 6.49 14.64 17.67 17.67 22.75 0.77
jnh205 3.59 6.17 6.28 7.90 10.08 0.50
jnh207 26.63 3.61 4.39 5.93 3.30 1.74
jnh209 6.22 7.45 6.07 6.73 6.44 0.46
jnh210 0.39 2.35 0.89 1.89 2.59 0.12
jnh212 78.00 70.92 29.77 27.28 112.84 6.31
jnh213 0.85 9.43 5.92 2.46 4.30 0.41
jnh217 0.56 5.76 2.23 3.50 2.00 0.16
jnh218 0.66 1.45 1.06 2.19 1.60 0.09
jnh220 28.85 10.17 18.08 8.95 20.18 2.98
jnh301 25.58 46.23 22.13 36.79 43.41 1.10


Table 9: Results of ASAP on class ii
          Accepted Time
Inst. n m Iterations Restarts Flips avg SDev
ii8a1 66 186 8 0 767 0.009 0.010
ii8a2 180 800 2 0 494 0.010 0.009
ii8a3 264 1552 3 0 1407 0.043 0.032
ii8a4 396 2798 7 0 4807 0.187 0.248
ii8b1 336 2068 1 0 759 0.014 0.005
ii8b2 576 4088 17 0 20590 0.460 0.336
ii8b3 816 6108 24 0 44949 0.996 0.538
ii8b4 1068 8214 31 0 78649 1.775 1.519
ii8c1 510 3065 1 0 881 0.019 0.005
ii8c2 950 6689 4 0 7806 0.186 0.111
ii8d1 530 3207 7 0 6192 0.153 0.249
ii8d2 930 6547 4 0 7707 0.198 0.145
ii8e1 520 3136 2 0 1886 0.050 0.021
ii8e2 870 6121 4 0 7842 0.214 0.117
ii16a1 1650 19368 6 0 20726 1.32 1.57
ii16a2 1602 21281 182 14 573916 32.60 28.66
ii16b1 1728 24792 7 0 22959 3.33 1.48
ii16b2 1076 16121 40 2 66398 7.39 2.73
ii16c1 1580 16467 20 0 46468 5.09 3.25
ii16c2 924 13803 46 2 67029 8.18 4.71
ii16d1 1230 15901 9 0 21051 3.15 2.51
ii16d2 836 12461 49 3 63324 8.85 6.40
ii16e1 1245 14766 2 0 4778 1.22 0.42
ii16e2 532 7825 30 1 24379 6.11 3.73
ii32a1 459 9212 47 2 28236 13.07 11.28
ii32b4 381 9618 675 56 312122 207.93 251.55
ii32c4 759 20862 83 6 91839 100.46 63.66
ii32d3 824 19478 254 20 292584 188.41 144.29
ii32e5 522 11636 173 8 122631 84.62 68.92


Table 10: Comparison of ASAP, GRASP and GSAT on class ii
Inst. ASAP GRASP-A GRASP-B GRASP-C GRASP-D GSAT
ii8a4 0.187 0.23 0.30 0.32 0.24 0.09
ii8b4 1.775 369.37 681.60 163.25 129.07 15.62
ii8c1 0.019 37.26 82.19 32.02 12.33 0.03
ii8d2 0.198 3.23 3.12 3.45 4.31 0.64
ii8e2 0.214 21.97 10.00 19.57 15.30 0.62
ii16a2 32.70 1970.58 - - - 1373.2
ii16b1 3.33 449.99 - - - 9.03
ii16c2 8.18 43.30 11.20 16.89 78.71 39.08
ii16d2 8.85 56.32 20.97 7.47 47.71 19.54
ii16e1 1.22 74.62 17.80 10.82 52.93 0.61
ii32a1 13.07 68.36 8.93 1.66 53.66 1.85
ii32b4 207.93 28.21 3.64 3.38 40.24 1.50
ii32c4 100.46 200.97 43.21 47.25 139.21 7.78
ii32d3 188.41 666.73 119.68 20.03 1136.34 22.91
ii32e5 84.72 16.47 2.31 3.21 24.17 1.75


Table 11: Machine Benchmark statistics: Runnuning time (seconds) of DIMACS test program dfmax on Pentium II and SGI Challenge
  machine SGI/P2 CPU
problem P2/350 SGI Time Ratio
r100.5.b 0.01 0.02 2
r200.5.b 0.41 0.58 1.49
r300.5.b 3.56 4.87 1.41
r400.5.b 22.21 30.35 1.45
r500.5.b 86.15 116.72 1.45



Next: Discussion Up: Results of Experiments Previous: Comparison with Evolutionary Algorithms
Claudio Rossi
1999-11-30