We consider the problems of determining the metric dimension and the minimum cardinality of doubly resolving sets in
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.
Published March 2017 , 11 pages