Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis

• QUBO is defined on a graph whose nodes are variables and whose edges carry weights c_ij.The node set is N and the edge set is E.Source: §1 · p. 1
• The objective maximizes the sum of diagonal terms c_ii x_i and edge terms c_ij x_i x_j, with each x_i in {0,1}.Source: §1 · p. 1
• Equivalently, QUBO is written as maximizing x^T Q x over x in {0,1}^n, where Q is an n-by-n symmetric coefficient matrix.Source: §1 · p. 2

QUBO and Ising literature

• QUBO models numerous optimization categories, and many NP-complete problems can be converted to Ising form for annealing-based search [14].Examples include network flows, scheduling, max-cut, max-clique, vertex cover, partitioning, covering, satisfiability, matching, and spanning tree.Source: §2 · p. 2

Solution approaches

• Modern metaheuristics can find good solutions to large NP-complete QUBOs, while quantum annealing hardware uses a Chimera qubit network and requires minor-embedding.Chimera connects densely linked groups of qubits sparsely to one another.Source: §2 · p. 2

Literature and contribution

• The paper presents four iterative rules to reduce the Q matrix, extending prior QUBO reduction work, and explores node-density transformations and sensitivity analysis.Earlier work achieved complete reduction for certain structured problems using roof duals and derivative rules, while flow-network methods help determine optimal assignments and lower bounds.Source: §2 · pp. 2–3

Problem scope

• The study targets connected, generally sparse Q matrices with some densely connected nodes and mostly uniform coefficients, but a small share of strong outliers, under the sparsity-of-variable-effects assumption.The rules apply to any QUBO, but the paper studies structures associated with real-world graphs and assumes a small percentage of variables have strong effects.Source: §2 · pp. 3–4

Novelty and test instances

• The authors describe these real-world-graph-like QUBO instances as the first problems of this type studied in the literature and provide the generator code and test set online.A typical 1,000-node, 5,000-edge instance has most coefficients between -10 and 10 and a small number of outliers between magnitudes 25 and 250; reduction removes many outliers.Source: §2 · p. 4

3. RULES FOR REDUCING Q TO SHRINK QUBO

• Rules 1 and 2 fix x_i to 1 or 0, respectively, when their coefficient-sum conditions guarantee that choice is optimal.Rule 1 requires c_ii + C_i^- ≥ 0; Rule 2 requires c_ii + C_i^+ ≤ 0. Rule 1 adjusts the objective and removes row and column i, while Rule 2 removes them without an objective adjustment; Rule 5 also eliminates a zero row because its variable has no objective effect.Source: §3 · pp. 5–6
• Rule 3 fixes x_i = x_h = 1 when Rule 1 fixes neither variable, c_ih > 0, and the stated combined coefficient sum is nonnegative.The condition is c_ii + c_hh + c_ih + C_i^- ≥ 0.Source: §3 · p. 5
• Rule 4 implies x_i + x_h ≤ 1 under its coefficient conditions, but does not predetermine either variable and was not implemented in this investigation.It applies when Rule 2 fixes neither variable, c_ih > 0, and c_ii + c_hh + c_ih + C_i^+ ≤ 0.Source: §3 · p. 6

4.1 Graph Expansion via Strongly Coupled Nodes

• Over-capacity nodes are expanded with strongly coupled nodes until the edge limit is met, producing a graph with an optimal solution equivalent to the original.The process may be continued until each node satisfies the imposed edge-capacity restriction.Source: §4.1 · p. 6
• Strong coupling uses M(x_i - 2x_ix_j + x_j), with large negative M in maximization, to force variables to share a value rather than both equal 1 as in Rule 3.For mapping to a physical graph such as the Chimera graph, the expanded graph is also subject to the edge-capacity restriction.Source: §4.1 · pp. 6–7
• Future work will combine Rules 1–5 with strong coupling to transform graphs to meet a target graph’s node and edge specifications.Source: §4.1 · p. 8

4.2 Use of the Rules in Sensitivity Analysis

• Rules 1–4 provide coefficient-change magnitudes indicating when a variable becomes determined or remains indeterminate, supporting sensitivity analysis of Q.For Rule 1, the threshold reflects the difference between a row’s linear coefficient and the sum of its negative quadratic coefficients.Source: §4.2 · pp. 8–9
• The paper did not specifically investigate sensitivity or robustness, though repeated tests with a random Q matrix checked the robustness of certain results.Similar sensitivity expressions can be developed for Rules 2 and 3.Source: §4.2 · p. 9

5. PSEUDOCODE

• The algorithm applies Rules 1–5, reduces Q, and repeats until no more variables are determined.Each reduction updates the row sums, and variables set to 1 trigger an objective-function adjustment by a constant.Source: §5 · pp. 9–10
• An array initializes each variable as unknown and records whether it is later determined to equal 0 or 1.The pseudocode uses -1 to indicate an undetermined variable.Source: §5 · pp. 9–10
• The implementation converts the input graph to an internal Q format and calculates positive and negative off-diagonal row sums.The input may use different graph-file formats and Q-matrix storage representations; the sums are dynamic and updated during reduction.Source: §5 · p. 9

6. TESTING

• The experiment used a 16-run fractional factorial design across three problem sizes and two densities, yielding 96 tests that varied six Q characteristics and measured reduction, objective quality, and time to best solution.All generated graphs were connected, but 1% of nodes were densely connected, with up to 50 edges per node in the densest setting; preprocessing could disconnect graphs into independently solvable components, which the paper leaves for future research.Source: §6 · pp. 10–11

6.1 Test Results Using Cplex

• Across 96 test runs, QPro reduced Q matrices by 30% on average versus about 5% for Cplex; QPro+Cplex averaged a 7x speedup and zero average objective difference.After removing tests 84 and 95, QPro+Cplex still improved the objective by about 8,000 on average for 10,000-variable, 10,000-edge problems and found a better solution on every problem. The rules yielded no reductions on highly structured maxcut or uniformly distributed, 10%-dense, 2,500-variable ORLIB problems.Source: §6.1 · pp. 12, 14

6.1.2 Interpretation of Cplex Results

• Large quadratic outliers were the strongest reduction driver: factor 4 had the largest impact across all six problem types, while coefficient-range increases tended to slightly decrease reduction.Increasing large quadratic coefficients promotes Rule 3, which can fix two variables and can change other variables into determined ones. The estimated average reduction was PR(f1, f2, f3, f4, f5, f6) = -3f1 + 8f3 + 16f4 + 5f3f4 + 30, with factor values in [-1, 1]; factor interactions were partly confounded, including factors 3 and 4.Source: §6.1.2 · pp. 14–16

6.1.3 Robustness of Results under Randomness

• Across 100 randomized instances of Problem 15, mean reduction was 15% ± 5% for 10,000 edges and 20% ± 3% for 5,000 edges, while the 10,000-variable types 3 and 16 consistently yielded very large reductions.Ten percent of the 10,000-edge Problem 15 instances produced no reductions, showing sensitivity to random Q changes. By contrast, 100 random samples of types 3 and 16 retained a narrow reduction distribution; those types were solved to optimality by QPro+Cplex in 0.01 seconds versus Cplex not entering branch-and-cut within 600 seconds, and QPro found over 7,000 reductions versus fewer than 40 for Cplex.Source: §6.1.3 · pp. 16–17, Figure 6 · p. 16, Figure 7 · p. 17

6.2 Test Results Using Path Relinking Metaheuristic

• QPro+PR2 was about 4x faster to a slightly better solution on average than PR2 alone.For 31 of 32 tests on 1,000-variable problems, both approaches found the same answer; QPro+PR2 was over 30x faster on three. On 5,000-variable problems, it consistently found better objectives and was slightly faster; improvements were greatest on 1,000-variable problems, possibly because PR2 parameters were not tuned for larger problems.Source: §6.2 · p. 18, Table 6 · p. 18

6. SUMMARY & CONCLUSIONS

• The study developed test problems with sparse connections, mostly uniformly distributed Q elements, and varying amounts of outliers to reflect unstructured, random business problems.Source: §6 · p. 20
• The principal contribution is five justified QUBO-reduction rules combined in rapid preprocessor QPro.The rules were tested with Cplex and tabu search incorporating path relinking.Source: §6 · p. 20
• Reduction is most influenced by the range of uniformly distributed Q elements and the number and magnitude of quadratic outliers.Source: §6 · p. 20
• QPro preprocessing is very fast and effective at reducing the time needed to obtain high-quality solutions.The implementation was tested with the exact Cplex solver and a tabu search metaheuristic incorporating path relinking.Source: §6 · p. 20
• The rules can also support sensitivity analysis and robustness, and transformations can increase problem size while reducing edge density per node.Source: §6 · p. 20

APPENDIX B. Detailed Test Results using QPro and Path Relinking Metaheuristic PR2

• The appendix identifies QPro + PR2 and PR2 default in its comparison of objective value and time across 96 test problems.The supplied passages provide the comparison's scope but no outcome values.Source: Appendix B · pp. 29–31