© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

INFORMS journal on computing

SSS Algorithms for Max-Cut

Claudio Gentile, Giovanni Rinaldi, Esteban Salgado

Published Jul 16, 2025• 0 citations

Abstract

The subgraph sampling scheme (SSS) is a technique originally introduced for Markov random fields. It is a powerful tool for designing heuristic algorithms for max-cut, quadratic unconstrained binary optimization (QUBO), and other optimization problems. The first application of SSS in combinatorial optimization, combined with dynamic programming, is in Selby’s heuristic. This algorithm is shown to outperform quantum annealing for solving max-cut problems on chimera graphs. Leveraging SSS, we introduce two new algorithms. One is designed to handle general graphs, whereas the other is specifically tailored for toroidal grid graphs. To assess the effectiveness of these algorithms, we conducted a comprehensive evaluation. We used the same methodology, test bed, and set of 37 well-established heuristics for max-cut and QUBO problems as described in a recent study of Dunning, Gupta, and Silberholz. Notably, all three SSS-based algorithms consistently achieve top rankings in terms of performance. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the funding program Horizon 2020 - Excellent Science - Marie Skłodowska-Curie Actions of the European Commission (Grant MINOA- Mixed-Integer Non-Linear Optimization Applications/764759]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0812 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0812 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

DOI: 10.1287/ijoc.2024.0812

Related papers

Recursive Quantum Relaxation for Combinatorial Optimization Problems

Ruho Kondo, Yuki Sato, Rudy Raymond +1 more

Quantum optimization methods use a continuous degree-of-freedom of quantum states to heuristically solve combinatorial problems, such as the MAX-CUT problem, which can be attributed to various NP-hard combinatorial problems. This paper shows that some existing quantum optimization methods can be unified into a solver to find the binary solution which is most likely measured from the optimal quantum state. Combining this finding with the concept of quantum random access codes (QRACs) for encoding bits into quantum states on fewer qubits, we propose an efficient recursive quantum relaxation method called recursive quantum random access optimization (RQRAO) for MAX-CUT. Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner using a tensor network technique, show that RQRAO not only outperforms the Goemans-Williamson and recursive QAOA methods, but also is comparable to state-of-the-art classical solvers. The code is available at https://github.com/ToyotaCRDL/rqrao.

arXiv:2403.02045•Quantum•Jan 15, 2025•10 citations

Faster exact solution of sparse MaxCut and QUBO problems

Daniel Rehfeldt, Thorsten Koch, Yuji Shinano

Abstract The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

Mathematical Programming Computation•Apr 15, 2023•38 citations

A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut

Gabriel Maliakal, Ismail Alkhouri, Alvaro Velasquez +2 more

The Maximum Cut (MaxCut) problem is NP-Complete, and obtaining its optimal solution is NP-hard in the worst case. As a result, heuristic-based algorithms are commonly used, though their design often requires significant domain expertise. More recently, learning-based methods trained on large (un)labeled datasets have been proposed; however, these approaches often struggle with generalizability and scalability. A well-known approximation algorithm for MaxCut is the Goemans-Williamson (GW) algorithm, which relaxes the Quadratic Unconstrained Binary Optimization (QUBO) formulation into a semidefinite program (SDP). The GW algorithm then applies hyperplane rounding by uniformly sampling a random hyperplane to convert the SDP solution into binary node assignments. In this paper, we propose a training-data-free approach based on a non-episodic reinforcement learning formulation, in which an agent learns to select improved rounding hyperplanes that yield better cuts than those produced by the GW algorithm. By optimizing over a Markov Decision Process (MDP), our method consistently achieves better cuts across large-scale graphs with varying densities and degree distributions.

arXiv:2505.13405•May 19, 2025•0 citations

Faster exact solution of sparse MaxCut and QUBO problems

Daniel Rehfeldt, Thorsten Koch, Yuji Shinano

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse MaxCut and QUBO instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

arXiv:2202.02305•Feb 4, 2022•1 citation

A Quantum Genetic Algorithm Framework For The MaxCut Problem

Paulo André Viana de Araújo

The MaxCut problem is a fundamental problem in Combinatorial Optimization, with sig- nificant implications across diverse domains such as logistics, network design, and statistical physics. The algorithm represents innovative approaches that balance theoretical rigor with practical scalability. The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles. By partition- ing graphs into manageable subgraphs, optimizing each independently, and applying graph contraction to merge the solutions, the method exploits the inherent binary symmetry of Max- Cut to ensure a more efficient and robust approximation performance. Theoretical analysis establishes a foundation for a better performance of the algorithm, while empirical evalua- tions provide quantitative evidence of its effectiveness. On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefi- nite Programming (SDP) approach, which provides up to 99.7% of the optimal solution for larger graphs. On Erdős-Rényi random graphs, the QGA demonstrates competitive perfor- mance, achieving median solutions within 92-96% of the SDP results. These results showcase the potential of the QGA framework to deliver competitive solutions, even under heuristic constraints, while demonstrating its promise for scalability as quantum hardware evolves.

•Jan 30, 2025•0 citations

A comprehensive benchmark of an Ising machine on the Max-Cut problem

Salwa Shaglel, Markus Kirsch, Mårten Winkler +4 more

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.

arXiv:2507.22117•New Journal of Physics•Jun 5, 2026•0 citations

The subgraph sampling scheme (SSS) is a technique originally introduced for Markov random fields. It is a powerful tool for designing heuristic algorithms for max-cut, quadratic unconstrained binary optimization (QUBO), and other optimization problems. The first application of SSS in combinatorial optimization, combined with dynamic programming, is in Selby’s heuristic. This algorithm is shown to outperform quantum annealing for solving max-cut problems on chimera graphs. Leveraging SSS, we introduce two new algorithms. One is designed to handle general graphs, whereas the other is specifically tailored for toroidal grid graphs. To assess the effectiveness of these algorithms, we conducted a comprehensive evaluation. We used the same methodology, test bed, and set of 37 well-established heuristics for max-cut and QUBO problems as described in a recent study of Dunning, Gupta, and Silberholz. Notably, all three SSS-based algorithms consistently achieve top rankings in terms of performance. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the funding program Horizon 2020 - Excellent Science - Marie Skłodowska-Curie Actions of the European Commission (Grant MINOA- Mixed-Integer Non-Linear Optimization Applications/764759]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0812 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0812 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Quantum optimization methods use a continuous degree-of-freedom of quantum states to heuristically solve combinatorial problems, such as the MAX-CUT problem, which can be attributed to various NP-hard combinatorial problems. This paper shows that some existing quantum optimization methods can be unified into a solver to find the binary solution which is most likely measured from the optimal quantum state. Combining this finding with the concept of quantum random access codes (QRACs) for encoding bits into quantum states on fewer qubits, we propose an efficient recursive quantum relaxation method called recursive quantum random access optimization (RQRAO) for MAX-CUT. Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner using a tensor network technique, show that RQRAO not only outperforms the Goemans-Williamson and recursive QAOA methods, but also is comparable to state-of-the-art classical solvers. The code is available at https://github.com/ToyotaCRDL/rqrao.

Abstract The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

The Maximum Cut (MaxCut) problem is NP-Complete, and obtaining its optimal solution is NP-hard in the worst case. As a result, heuristic-based algorithms are commonly used, though their design often requires significant domain expertise. More recently, learning-based methods trained on large (un)labeled datasets have been proposed; however, these approaches often struggle with generalizability and scalability. A well-known approximation algorithm for MaxCut is the Goemans-Williamson (GW) algorithm, which relaxes the Quadratic Unconstrained Binary Optimization (QUBO) formulation into a semidefinite program (SDP). The GW algorithm then applies hyperplane rounding by uniformly sampling a random hyperplane to convert the SDP solution into binary node assignments. In this paper, we propose a training-data-free approach based on a non-episodic reinforcement learning formulation, in which an agent learns to select improved rounding hyperplanes that yield better cuts than those produced by the GW algorithm. By optimizing over a Markov Decision Process (MDP), our method consistently achieves better cuts across large-scale graphs with varying densities and degree distributions.

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse MaxCut and QUBO instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

The MaxCut problem is a fundamental problem in Combinatorial Optimization, with sig- nificant implications across diverse domains such as logistics, network design, and statistical physics. The algorithm represents innovative approaches that balance theoretical rigor with practical scalability. The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles. By partition- ing graphs into manageable subgraphs, optimizing each independently, and applying graph contraction to merge the solutions, the method exploits the inherent binary symmetry of Max- Cut to ensure a more efficient and robust approximation performance. Theoretical analysis establishes a foundation for a better performance of the algorithm, while empirical evalua- tions provide quantitative evidence of its effectiveness. On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefi- nite Programming (SDP) approach, which provides up to 99.7% of the optimal solution for larger graphs. On Erdős-Rényi random graphs, the QGA demonstrates competitive perfor- mance, achieving median solutions within 92-96% of the SDP results. These results showcase the potential of the QGA framework to deliver competitive solutions, even under heuristic constraints, while demonstrating its promise for scalability as quantum hardware evolves.

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.