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.

此研究提出了一种通过识别可以预定的最优变量来减少 QUBO 矩阵的规模并从而改善优化问题解决质量和时间的方法，并分析了对此规模减小技术最有影响的 QUBO 结构特征。