  The tabu and restart are two fundamental strategies for local search. In this
paper, we improve the local search algorithms for solving the Maximum Weight
Clique (MWC) problem by introducing new tabu and restart strategies. Both the
tabu and restart strategies proposed are based on the notion of a local search
scenario, which involves not only a candidate solution but also the tabu status
and unlocking relationship. Compared to the strategy of configuration checking,
our tabu mechanism discourages forming a cycle of unlocking operations. Our new
restart strategy is based on the re-occurrence of a local search scenario
instead of that of a candidate solution. Experimental results show that the
resulting MWC solver outperforms several state-of-the-art solvers on the
DIMACS, BHOSLIB, and two benchmarks from practical applications.
