Quadratic Unconstrained Binary Optimization Problem Preprocessing:
  Theory and Empirical Analysis
  The Quadratic Unconstrained Binary Optimization problem (QUBO) has become a
unifying model for representing a wide range of combinatorial optimization
problems, and for linking a variety of disciplines that face these problems. A
new class of quantum annealing computer that maps QUBO onto a physical qubit
network structure with specific size and edge density restrictions is
generating a growing interest in ways to transform the underlying QUBO
structure into an equivalent graph having fewer nodes and edges. In this paper
we present rules for reducing the size of the QUBO matrix by identifying
variables whose value at optimality can be predetermined. We verify that the
reductions improve both solution quality and time to solution and, in the case
of metaheuristic methods where optimal solutions cannot be guaranteed, the
quality of solutions obtained within reasonable time limits.
  We discuss the general QUBO structural characteristics that can take
advantage of these reduction techniques and perform careful experimental design
and analysis to identify and quantify the specific characteristics most
affecting reduction. The rules make it possible to dramatically improve
solution times on a new set of problems using both the exact Cplex solver and a
tabu search metaheuristic.
