Groupe d’études et de recherche en analyse des décisions

G-2017-17

An IP-based swapping algorithm for the metric dimension and minimal doubly resolving set problems in hypercubes

We consider the problems of determining the metric dimension and the minimum cardinality of doubly resolving sets in \(n\)-cubes. Most heuristics developed for these two NP-hard problems use a function that counts the number of pairs of vertices that are not (doubly) resolved by a given subset of vertices, which requires an exponential number of distance evaluations, with respect to \(n\). We show that it is possible to determine whether a set of vertices (doubly) resolves the \(n\)-cube by solving an integer program with \(O(n)\) variables and\(O(n)\) constraints. We then demonstrate that small resolving and doubly resolving sets can easily be determined by solving a series of such integer programs within a swapping algorithm. Results are given for hypercubes having up to a quarter of a billion vertices, and new upper bounds are reported.

, 11 pages