Matheuristic Fixed Set Search Applied to the K-Dominating Set Problem

In a wide range of real-world covering problems, like finding the optimal locations of electric vehicle charging stations, it is of high importance to have resistance to component failures. One effective way of modeling this type of robustness is the k-dominating set problem. Solving this problem is computationally challenging due to its $\mathcal{N} \mathcal{P}$-hardness. This challenge is tackled by employing the fixed search set (FSS) metaheuristic. The Matheuristic Fixed Set Search (MFSS) is applied, which combines mathematical programming and the FSS learning mechanism. We perform extensive computational experiments on commonly used benchmark instances, comparing the algorithm’s performance against the well-known GRASP metaheuristic and the commercial solver CPLEX. The experimental findings show that the proposed MFSS algorithm produces highly competitive results at a lower computational cost.