Advancing Tabu and Restart in Local Search for Maximum Weight Cliques
This work addresses a combinatorial optimization problem with applications in various domains, but it is incremental as it builds on existing local search methods.
The paper tackled the Maximum Weight Clique problem by introducing new tabu and restart strategies based on local search scenarios, resulting in a solver that outperforms state-of-the-art solvers on multiple benchmarks.
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.