In this paper we consider two similar NP-hard optimization problems on graphs: the metric dimension problem and the problem of determining minimal doubly resolving sets. Both arise in many diverse areas, including network discovery and verification, robot navigation, chemistry, etc. For each problem we propose a new mathematical programming formulation and test it with CPLEX and Gurobi, the two well-known exact solvers. Moreover, for solving more realistic large size instances, we design Variable Neighborhood Search based heuristic. An extensive experimental comparison on four different types of instances indicates that our VNS approach consistently outperforms genetic algorithm, the only existing heuristic in the literature designed for solving those problems.