### G-2017-17

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

## Alain Hertz

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.

Published **March 2017**
,
11 pages