Yongliang Sun

Cheng-Han Huang, Yongliang Sun, Chaoyan Huang et al.

Many combinatorial optimization problems admit quadratic unconstrained binary formulations (QUBO) which can often be relaxed to the box $[0,1]^n$ and optimized using scalable gradient-based methods. However, the resulting non-convex landscape can often contain local optima that are spurious or infeasible. In this paper, we establish sufficient structural conditions on quadratic penalties that rule out these failures, guaranteeing that every local minimizer of the relaxed problem is both binary and feasible. For each problem we study, we examine existing QUBO formulations when available, identify why they fail when they do, and propose alternative relaxed QUBOs that satisfy our conditions. We show for several common combinatorial problems, including open-pit mining, 0--1 knapsack, and traveling salesman formulations, that these constructions allow gradient-based methods such as projected gradient descent and Adam to be safely applied to obtain valid binary solutions. Our results clarify when differentiable optimization is a reliable local solver for quadratic combinatorial objectives.

Yongliang Sun, Ismail Alkhouri, Cheng-Han Huang et al.

Recent studies suggest that gradient-based methods applied to relaxed box-constrained Quadratic Unconstrained Binary Optimization (QUBO) formulations can outperform classical heuristics in some large-scale regimes, often relying on heavy parallelization. However, these methods still underperform heuristics in other settings. In this work, we clarify this apparent discrepancy through a detailed analysis of the relaxed non-convex QUBO local maxima for both the Maximum Independent Set (MIS) and Maximum Cut (MaxCut) problems, and by introducing a new quadratic objective for MaxCut. Motivated by this analysis, we propose a mutation-based differentiable global reset algorithm, combined with local search to escape local maxima. We term our approach mQO, standing for mutation-based Quadratic combinatorial Optimization. The proposed strategy dramatically improves the performance of gradient-based solvers without heavy reliance on GPU parallelized initializations, indicating that stalling, rather than model capacity or compute, is the dominant bottleneck. As a result, on large-scale graphs, mQO achieves superior performance against state-of-the-art heuristics, commercial integer programming solvers, and recent GPU methods.