The software corresponding to the HAMMING-REACTIVE-TABU-SEARCH
algorithm has been developed in C++
and the algorithm has been tested on the benchmark described in Sec. 3.4.
For GSAT and GSAT-with-walk, the data in
[30] are not sufficient because we are interested in analyzing
the approximation behavior as a function of the number of iterations.
Therefore both algorithms are developed in C++ and new tests
are run on the same benchmark.
The original seeds were not available and therefore the tasks are
different from those used in [30], although, clearly,
extracted from the same distribution. The parameter MAX-FLIPS
used
is 
,
the probability p for GSAT-with-walk is 0.5 and
MAX-TRIES corresponds to the desired total number of iterations.
Figure: MAX-3-SAT: the H-RTS algorithm (Hamming-Reactive Tabu Search)
up to 1,000 n iterations.
The results for GSAT and GSAT-with-walk(0.5) are reported with
dashed lines for a comparison.
All algorithms are run for a total of 
iterations, a number
such that a ``plateau'' in the performance of HAMMING-REACTIVE-TABU-SEARCH
is reached
and additional iterations do not produce significantly better results
(up to 
iterations have been allowed).
Fig. 12 compares the average results
of H-RTS (with initial value 
)
with those of GSAT and GSAT-with-walk(0.5) on the
MAX-3-SAT tasks, with dimensions n from 100 to 500.
It is apparent that, for a given number of allotted iterations,
H-RTS reaches a much lower number of unsatisfied clauses,
especially in the initial part of the search. In fact,
H-RTS reaches in the initial phase
a number of unsatisfied clauses
that is not too far from the value obtained after a very long search.
For example, for the 500:5000 tasks, 170 unsatisfied clauses (on the
average) are reached by H-RTS at
1,000 iterations, while GSAT and GSAT-with-walk(0.5) need
more than 50,000. 160 unsatisfied clauses are reached at
20,000 iterations, while the two competing
algorithms are still far from that value after
500,000 iterations.
For the larger-dimensional 1000:10000 MAX-3-SAT tasks, 340 unsatisfied clauses are reached after 1,500 iterations by H-RTS, after 48,000 by GSAT, after 817,000 by GSAT-with-walk(0.5). 330 unsatisfied clauses are reached after 3,200 iterations by H-RTS. GSAT comes close to that value (330.16) at 1,000,000 iterations, while GSAT-with-walk(0.5) is still stuck at 339.38. Only H-RTS reaches a value lower than 320 unsatisfied clauses, at 44,000 iterations.
A similar remarkable performance difference is obtained on the MAX-4-SAT tasks. For example, on the 1000:10000 tasks, 20 unsatisfied clauses are reached at 4,000 iterations by H-RTS, while GSAT and GSAT-with-walk are still stuck at 21.72 and 23.66 unsatisfied clauses, respectively, after 1,000,000 iterations.
The average
values obtained for all problem dimensions
with the complete runs of 
iterations
are collected in Table 2 and Table 3.
Let us note that the CPU times for the runs are affordable. As an example, in our implementation (C++, GNU g++ compiler, Pentium PC with Linux at 120 MHz) the CPU time needed to execute 10,000 iterations is of 4.0 seconds on a 500:5000 MAX-3-SAT task, 7.6 sec on a 1000:10000 MAX-3-SAT task, 9.2 sec on a 1000:10000 MAX-4-SAT task. A detailed analysis of the CPU times is not presented in this paper for brevity reasons. On the other hand, the times on different machines can be easily obtained by the readers by compiling and running the C++ software that is an integral part of this paper.