A Scatter Search Metaheuristic and Improvements to an Exact Algorithm for the Weighted Safe Set Problem

Given a connected undirected graph with weighted vertices, the Weighted Safe Set Problem amounts to labelling all vertices either as safe or unsafe, in such a way that the total weight of each connected component induced by safe vertices is not exceeded by the total weight of any adjacent connected component induced by the unsafe ones. The aim is to satisfy this requirement with a minimum weight subset of safe vertices. This paper proposes a new Scatter Search metaheuristic based on the idea of merging feasible solutions of good quality or highly diversified and reduce them by removing redundant elements. We also revise an existing combinatorial branch-and-bound algorithm, introducing a slightly weaker relaxation that, on the other hand, allows to exploit stronger reduction procedures and a more effective branching strategy. These enhancements and the improved upper bounds provided by Scatter Search reduce the computational effort to find optimal solutions and mitigates the issue of memory exhaustion that affected the exact algorithm on some benchmark instances with more than 50 vertices.