Enhancing MaxCut Solutions: Dynex’s Benchmark Performance on G70 Using Quantum Computing

We conducted an experiment on the G70 MaxCut problem, a complex unweighted MaxCut challenge with 10,000 nodes and 9,999 edges sourced from the publicly available Gset dataset provided by Stanford University. Various algorithms and solvers were evaluated, including commercial solvers like Gurobi and IBM CPLEX, and specialized algorithms such as the SDP solver DSDP, the graph neural network-based PI-GNN, and the tabu search-based KHLWG. Utilizing Dynex’s neuromorphic quantum computing cloud with a single Nvidia RTX3080 GPU, and without any MaxCut-specific enhancements, Dynex achieved a Maximum Cut value of 9,506 — outperforming other algorithms and demonstrating the potential of the Dynex platform. The experiment underscores that additional computational resources or bespoke algorithmic modifications could potentially lead to even higher performance, potentially setting new benchmarks for MaxCut solutions and showcasing the scalability and adaptability of the Dynex platform for tackling such optimization problems.

MaxCut is a fundamental problem in combinatorial optimization and graph theory, where the task is to divide the vertices of a graph into two groups such that the number of edges between the two groups is maximized. This problem is significant both theoretically and practically, as it belongs to the class of NP-complete problems, making it computationally challenging to solve for large graphs. MaxCut has a wide range of applications across various fields, including circuit layout design, network design, and statistical physics, where it helps in modeling phenomena such as spin glasses. The complexity and utility of MaxCut also make it a popular benchmark for testing the effectiveness of new computational methods, including heuristic algorithms, approximation algorithms, and more recently, quantum algorithms.

We conducted the experiment using standard MaxCut benchmark instances drawn from the publicly available Gset dataset, which is frequently employed for evaluating MaxCut algorithms and is provided by Stanford University. Specifically, we selected G70, an unweighted MaxCut problem on a sparse random graph comprising 10,000 nodes and 9,999 edges, for our analysis. This graph was chosen due to its complexity; the optimal cut is not yet known, making it a suitable candidate for benchmarking our computational approach[1].

The algorithms and solvers included in our comparison include the commercial solvers Gurobi and IBM ILOG CPLEX as well as a number of special purpose algorithms created to solve MaxCut problems: DSDP is an SDP solver based on dual-scaling algorithm, PI-GNN is an unsupervised learning method to solve graph partitioning problems based on graph neural networks and KHLWG is a tabu search based algorithm specifically designed to solve large MaxCut instances.

To evaluate the performance of Dynex, the G70 problem was transformed into a binary quadratic model and subsequently solved using the Dynex neuromorphic quantum computing cloud, utilising only one Nvidia RTX3080 GPU. This evaluation was conducted without the implementation of any MaxCut-specific enhancements or algorithmic optimisations, which could potentially augment the results obtained by Dynex’s sampler. Notably, even in the absence of tailored algorithms for MaxCut, Dynex demonstrated superior performance compared to other solvers and algorithms utilized in this experiment.

The graphic reports the best results achieved by Dynex during 10 sweeps and the comparison solvers and algorithms. For Gurobi, IBM CPLEX, DSDP, PI-GNN and KHLW we directly use the results presented in the referenced papers as their performance is highly dependent on the implementation and the stochastic nature of heuristic techniques would inevitably lead to deviations to the results presented in the papers.

The greater the Maximum Cut value obtained, the more optimal the solution. Dynex computed a solution with a Maximum Cut value of 9,506, representing the highest achievement among all results in this comparison. For reference, commercial solver Gurobi reached a Maximum Cut value of 9,490, while IBM CPLEX reported a value of 9,473 in [2]. The SDP-based algorithm DSDP attained a result of 9,456 [3], PI-GNN achieved a maximum of 9,421 [4], and the tabu-based local search algorithm KHLWG recorded a value of 9,458 [5].

Utilising additional computational resources from the Dynex cloud, or incorporating problem-specific modifications to the algorithm, holds the potential to enhance the performance on the G70 MaxCut problem significantly. By scaling up the computational power or tailoring the algorithmic approach to better fit the specific characteristics of the MaxCut problem, it is conceivable that the Dynex platform could achieve results surpassing the currently known best outcomes. Such improvements could redefine the benchmarks for MaxCut solutions.

All source codes of the experiment, the problem formulation and the results are available online:
https://github.com/dynexcoin/DynexSDK/tree/main/maxcut

Further reading:

• DePIN: Cryptocurrency Dynex (DNX): What it is, history, uses and outlook (Medium)
• Dynex Marketplace
• Dynex Website
• Introduction Video
• Book: A complete guide to Neuromorphic Computing (Amazon)

References:

[1] Rodriguez-Fernandez, A.E.; Gonzalez-Torres, B.; Menchaca-Mendez, R.; Stadler, P.F. Clustering Improves the Goemans–Williamson Approximation for the Max-Cut Problem. Computation 2020, 8, 75.

[2] Chase Cook, Hengyang Zhao, Takashi Sato, Masayuki Hiromoto, Sheldon X.-D. Tan, GPU-based Ising computing for solving max-cut combinatorial optimization problems, Integration, Volume 69, 2019, Pages 335–344, ISSN 0167–9260

[3] C. Choi and Y. Ye, Solving sparse semidefinite programs using the dual scaling algorithm with an iterative solver, Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA, 52242 (2000)

[4] M. J. Schuetz, J. K. Brubaker, and H. G. Katzgraber, Combinatorial optimization with physics-inspired graph neural networks, Nature Machine Intelligence, 4 (2022), pp. 367–377

[5] Kochenberger, Gary & Hao, Jin-Kao & Lü, Zhipeng & Wang, Haibo & Glover, Fred. (2013). Solving large scale Max Cut problems via tabu search. Journal of Heuristics. 19. 10.1007/s10732–011–9189–8