|Affiliations:||Mathematical Institute of the Serbian Academy of Sciences and Arts||Title:||Variable neighborhood search for metric dimension and minimal doubly resolving set problems||Journal:||European Journal of Operational Research||Volume:||220||Issue:||2||First page:||328||Last page:||337||Issue Date:||16-Jul-2012||Rank:||M21a||ISSN:||0377-2217||DOI:||10.1016/j.ejor.2012.02.019||Abstract:||
In this paper, two similar NP-hard optimization problems on graphs are considered: the metric dimension problem and the problem of determining a doubly resolving set with the minimum cardinality. Both are present in many diverse areas, including network discovery and verification, robot navigation, and chemistry. For each problem, a new mathematical programming formulation is proposed. For solving more realistic large-size instances, a variable neighborhood search based heuristic is designed. An extensive experimental comparison on five different types of instances indicates that the VNS approach consistently outperforms a genetic algorithm, the only existing heuristic in the literature designed for solving those problems.
|Keywords:||Combinatorial optimization | Metaheuristics | Metric dimension | Minimal doubly resolving set | Variable neighborhood search||Publisher:||Elsevier||Project:||Mathematical Modelas and Optimization Methods on Large-Scale Systems
Graph theory and mathematical programming with applications in chemistry and computer science
Show full item record
checked on Dec 6, 2023
checked on Dec 7, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.