  A minimum dominating set in a graph is a minimum set of vertices such that
every vertex of the graph either belongs to it, or is adjacent to one vertex of
this set. This mathematical object is of high relevance in a number of
applications related to social networks analysis, design of wireless networks,
coding theory, and data mining, among many others. When vertex weights are
given, minimizing the total weight of the dominating set gives rise to a
problem variant known as the minimum weight dominating set problem. To solve
this problem, we introduce a hybrid matheuristic combining a tabu search with
an integer programming solver. The latter is used to solve subproblems in which
only a fraction of the decision variables, selected relatively to the search
history, are left free while the others are fixed. Moreover, we introduce an
adaptive penalty to promote the exploration of intermediate infeasible
solutions during the search, enhance the algorithm with perturbations and node
elimination procedures, and exploit richer neighborhood classes. Extensive
experimental analyses on a variety of instance classes demonstrate the good
performance of the algorithm, and the contribution of each component in the
success of the search is analyzed.
