Mutation-Guided Differentiable Quadratic Combinatorial Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918489001820160 |
|---|---|
| author | Sun, Yongliang Alkhouri, Ismail Huang, Cheng-Han Velasquez, Alvaro Jha, Susmit Wang, Rongrong |
| author_facet | Sun, Yongliang Alkhouri, Ismail Huang, Cheng-Han Velasquez, Alvaro Jha, Susmit Wang, Rongrong |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_06921 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Mutation-Guided Differentiable Quadratic Combinatorial Optimization Sun, Yongliang Alkhouri, Ismail Huang, Cheng-Han Velasquez, Alvaro Jha, Susmit Wang, Rongrong Discrete Mathematics 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. |
| title | Mutation-Guided Differentiable Quadratic Combinatorial Optimization |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2605.06921 |