Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems

Technical Summary: Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems

Problem Statement
Combinatorial optimization problems are frequently encountered in fields such as logistics, materials design, and portfolio optimization. While many of these problems are NP-hard and require heuristic approaches, a significant barrier exists in their implementation on "Ising machines" (including quantum annealing hardware and physics-inspired solvers). Most existing hardware platforms accept input exclusively in the Quadratic Unconstrained Binary Optimization (QUBO) format, which restricts objective functions to linear and quadratic terms of binary variables.

However, numerous real-world problems, such as polymer sampling, protein folding, and specific routing tasks, inherently involve higher-order interactions (cubic, quartic, etc.). To solve these on standard hardware, researchers must apply "order-reduction" techniques to transform Polynomial Unconstrained Binary Optimization (PUBO) problems into QUBO form. This process introduces auxiliary variables and penalty terms to maintain logical consistency. The authors posit that this transformation inevitably increases the problem size and structural complexity, potentially degrading solution quality and stability, yet the specific impact of directly handling higher-order terms versus reducing them has not been thoroughly quantified on a unified platform for practical, large-scale instances.

Methodology
To address this gap, the study employs a comparative evaluation framework using the Fixstars Amplify Annealing Engine (Amplify AE). This high-performance solver, based on Simulated Annealing (SA) and large-scale GPU parallelization, offers two distinct modes:

1. PUBO Solver: Directly optimizes objective functions containing up to fourth-order terms without modification.
2. QUBO Solver: Solves the same problems after applying the substitution method for order reduction. This method replaces products of binary variables with new auxiliary variables and enforces constraints via penalty terms (specifically, $x_1x_2 = y_{1,2}$).

The study compares these two approaches on two benchmark problems that naturally contain higher-order terms:

• Low Autocorrelation Binary Sequence (LABS): A problem seeking binary sequences with minimal autocorrelation energy. The energy function involves squared autocorrelation terms, resulting in fourth-order interactions ($s_i s_{i+k} s_j s_{j+k}$).
• Vehicle Routing Problem (VRP) with Distance Balancing: A multi-objective problem minimizing total travel distance while simultaneously minimizing the variance of distances among vehicles. The variance term introduces fourth-order interactions when expanded.

Experiments were conducted with fixed computational times (60 seconds) across various problem sizes. For LABS, sequence lengths ($N$) ranged from 5 to 99. For VRP, the number of customer locations ($P$) and vehicles ($V$) were varied. The QUBO solver utilized a fixed penalty coefficient ($p=1$) for the substitution method, while the PUBO solver required no such parameter tuning.

Key Contributions and Results
The paper provides a quantitative analysis of the trade-offs between direct PUBO formulation and reduced QUBO formulation:

1. Solution Quality and Stability:

   • LABS: The PUBO solver consistently achieved lower normalized energy values (closer to the optimal solution) with significantly smaller standard deviations compared to the QUBO solver. The performance gap widened as the sequence length $N$ increased.
   • VRP: In single-instance analysis, the PUBO solver produced more stable trade-offs between total distance and distance variance. Scatter plots revealed that QUBO solutions were widely scattered and failed to reach the true minimum variance region, whereas PUBO solutions concentrated near the Pareto front.
   • Hypervolume Analysis: Across 30 randomly generated VRP instances, the PUBO solver consistently achieved larger hypervolume indicators (a measure of solution set diversity and quality) than the QUBO solver, confirming its superiority in multi-objective optimization.

2. Variable Expansion:

   • The study quantified the "variable explosion" caused by order reduction. For both LABS and VRP, the number of binary variables in the QUBO formulation grew rapidly with problem size, reaching tens of times the number of variables in the direct PUBO formulation for large instances. This expansion enlarges the search space, contributing to the observed degradation in solution stability.

3. Sensitivity to Penalty Coefficients:

   • The authors investigated the sensitivity of the QUBO approach to the penalty coefficient ($p$) used in the substitution method. A heatmap analysis for the LABS problem demonstrated that the optimal penalty coefficient varies significantly with problem size ($N$). No single value of $p$ provided consistent performance across all scales, highlighting the difficulty of tuning reduced formulations for general application.

Significance and Claims
The paper claims that directly handling higher-order terms via PUBO formulations offers distinct advantages over traditional order-reduction methods when solving combinatorial optimization problems on modern Ising-type hardware. The primary significance lies in the demonstration that:

• Structural Integrity: Preserving the original problem structure (PUBO) avoids the artificial expansion of the search space caused by auxiliary variables.
• Robustness: Direct formulation eliminates the need for tuning penalty coefficients, which are sensitive to problem scale and can destabilize the search process.
• Scalability: The PUBO approach maintains superior solution quality and stability as problem sizes increase, whereas the QUBO approach suffers from the compounding effects of variable expansion and constraint enforcement.

The authors conclude that while order reduction has been effective for various problems, the direct PUBO formulation represents a promising approach for practical, large-scale optimization scenarios, offering both structural simplicity and computational stability. The study suggests that future hardware and solver developments should continue to support direct higher-order execution to fully leverage these benefits in real-world applications.