Though empirical testing is broadly used to evaluate heuristics, there are major shortcomings with how it is applied in practice. In a systematic review of Max-Cut and Quadratic Unconstrained Binary Optimization (QUBO) heuristics papers, we found only 4% publish source code, only 10% compare heuristics with identical hardware and termination criteria, and most experiments are performed with an articial, homogeneous set of problem instances. To address these limitations, we rst propose a framework for reproducible heuristic evaluation based on large-scale open-source implementation, expanded sets of test instances, and evaluation with cloud computing. We give a proof of concept of the framework by testing 37 Max-Cut and QUBO heuristics across 3,298 problem instances. This large-scale evaluation provides insight into the types of problem instances for which each heuristic performs well or poorly. Because no single heuristic outperforms all others across all problem instances, we use machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners. We hope our framework will be applied broadly to identify \what works best when among heuristics for a range of optimization problems.
Though empirical testing is broadly used to evaluate heuristics, there are major shortcomings with how it is applied in practice. In a systematic review of Max-Cut and Quadratic Unconstrained Binary Optimization (QUBO) heuristics papers, we found only 4% publish source code, only 10% compare heuristics with identical hardware and termination criteria, and most experiments are performed with an articial, homogeneous set of problem instances. To address these limitations, we rst propose a framework for reproducible heuristic evaluation based on large-scale open-source implementation, expanded sets of test instances, and evaluation with cloud computing. We give a proof of concept of the framework by testing 37 Max-Cut and QUBO heuristics across 3,298 problem instances. This large-scale evaluation provides insight into the types of problem instances for which each heuristic performs well or poorly. Because no single heuristic outperforms all others across all problem instances, we use machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners. We hope our framework will be applied broadly to identify \what works best when among heuristics for a range of optimization problems.
Quadratic Unconstrained Binary Optimization (QUBO) provides a versatile framework for representing NP-hard combinatorial problems, yet existing solvers often face trade-offs among speed, accuracy, and scalability. In this work, we introduce a quantum-inspired solver (QIS) that unites branch-and-bound pruning, continuous gradient-descent refinement, and quantum-inspired heuristics within a fully adaptive control architecture. We benchmark QIS3 against eight state-of-the-art solvers, including genetic algorithms, coherent Ising machines, simulated bifurcation, parallel tempering, simulated annealing, our prior QIS2 version, D-Wave's simulated-annealing (Neal), and Gurobi on three canonical QUBO problem classes: Max-Cut, NAE-3SAT, and Sherrington-Kirkpatrick spin glass problems. Under a uniform runtime budget, QIS3 attains the best solution on nearly all instances, achieving optimality in 94% of max-cut instances. These results establish QIS3 as a robust, high-performance solver that bridges classical exact strategies and quantum-inspired heuristics for scalable QUBO optimization.
This study addresses the formidable challenge of solving large-scale Max-Cut problems (MCP). We introduce a rapid computational procedure utilizing a hybrid 1-flip/r-flip local search heuristic. This innovative strategy significantly reduces the computational time required for MCP problems while consistently generating solutions of exceptional quality. The paper presents substantial computational insights, showcasing the effectiveness of our approach on large-scale Max-Cut instances with varying densities. Our proposed heuristic is rigorously evaluated by comparing its performance against a quantum annealing solver, leveraging a multi-start Tabu Search framework. The results underscore the potency of this unique combination as an efficient and effective solution for large-scale QUBO problems. Notably, our hybrid heuristic consistently delivers high-quality solutions within the stringent CPU time limits of 600 seconds, demonstrating its efficacy across Max-Cut instances ranging from 10,000 to 40,000 variables. This research contributes to advancing the state-of-the-art in large-scale QUBO problem-solving, offering a powerful and time-efficient approach with broad applicability.
In this study, we address the formidable challenge of solving large-scale Max-Cut problems (MCP). We introduce a rapid computational procedure utilizing a hybrid 1-flip/r-flip local search heuristic. This innovative strategy significantly reduces the computational time required for MCP problems while consistently generating solutions of exceptional quality. The paper presents substantial computational insights, showcasing the effectiveness of our approach on very-large-scale Max-Cut instances with varying densities. Our proposed heuristic is rigorously evaluated by comparing its performance against a quantum annealing solver, leveraging a multi-start Tabu Search framework. The results underscore the potency of this unique combination as an efficient and effective solution for large-scale QUBO problems. Notably, our hybrid heuristic consistently delivers high-quality solutions within the stringent CPU time limits of 600 seconds, demonstrating its efficacy across Max-Cut instances ranging from 10,000 to 40,000 variables. This research contributes to advancing the state-of-the-art in large-scale QUBO problem-solving, offering a powerful and time-efficient approach with broad applicability.
Abstract Quadratic unconstrained binary optimization (QUBO) formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum–classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.
Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers provide optimal solutions but often face scalability limitations, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) formulations as alternative optimization paradigms. This work presents a systematic and reproducible empirical evaluation of QUBO-based scheduling methods against established classical baselines, including MILP, CP-SAT, GA, and HEFT. We evaluate three QUBO variants, single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule, together with hybrid enhancement strategies on both ground-truth validation workflows (3–4 tasks) and synthetic scaling instances (5–20 tasks). All solvers are assessed through a unified evaluation pipeline that explicitly tracks feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. Results show that all approaches recover the expected optimal makespan on validation instances, confirming formulation correctness. However, feasibility degradation emerges for specific QUBO variants as constraint interactions intensify, particularly when communication costs are introduced. Penalty sensitivity analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments delineate the regimes in which classical solvers and heuristics remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. Overall, the study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for heterogeneous HPC scheduling and identifies the regimes where classical approaches remain preferable under current formulations and solver capabilities.
Due to the expected disparity in quantum vs. classical clock speeds, quantum advantage for branch and bound algorithms is more likely achievable in settings involving large search trees and low operator evaluation costs. Therefore, in this paper, we describe and experimentally validate an exact classical branch and bound solver for quadratic unconstrained binary optimization (QUBO) problems that matches these criteria. Our solver leverages cheap-to-implement bounds from the literature previously proposed for Ising models, including that of Hartwig, Daske, and Kobe from 1984. We detail a variety of techniques from high-performance computing and operations research used to boost solver performance, including a global variable reordering heuristic, a primal heuristic based on simulated annealing, and a truncated computation of the recursive bound. We also outline a number of simple and inexpensive bound extrapolation techniques. Finally, we conduct an extensive empirical analysis of our solver, comparing its performance to state-of-the-art QUBO and MaxCut solvers, and discuss the challenges of a speedup via quantum branch and bound beyond those faced by any quadratic quantum speedup.