  A major limitation of current generations of quantum annealers is the sparse
connectivity of manufactured qubits in the hardware graph. This technological
limitation generated considerable interest, motivating efforts to design
efficient and adroit minor-embedding procedures that bypass sparsity
constraints. In this paper, starting from a previous equational formulation by
Dridi et al. (arXiv:1810.01440), we propose integer programming (IP) techniques
for solving the minor-embedding problem. The first approach involves a direct
translation from the previous equational formulation to IP, while the second
decomposes the problem into an assignment master problem and fiber condition
checking subproblems. The proposed methods are able to detect instance
infeasibility and provide bounds on solution quality, capabilities not offered
by currently employed heuristic methods. We demonstrate the efficacy of our
methods with an extensive computational assessment involving three different
families of random graphs of varying sizes and densities. The direct
translation as a monolithic IP model can be solved with existing commercial
solvers yielding valid minor-embeddings, however, is outperformed overall by
the decomposition approach. Our results demonstrate the promise of our methods
for the studied benchmarks, highlighting the advantages of using IP technology
for minor-embedding problems.
