Next: Discussion
Up: Results of Experiments
Previous: Comparison with Evolutionary 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