A Novel Algorithm Based on the Bundle Method for Solving the Max-Cut Problem
Fadhl Jawad Kadhim, Ahmed Sabah Al-Jilawi · AppliedMath · 2025
A novel algorithm was proposed for solving the max-cut problem, which seeks to identify the cut with the maximum weight in a given graph. Our technique is based on the bundle approach, applied to a newly formulated semidefinite relaxation. This research establishes the theoretical convergence of our approximation technique and presents the numerical results obtained on several large-scale graphs from the BiqMac library, specifically with 100, 250, and 500 nodes. The resulting performance was compared with that produced by two alternative semidefinite programming-based approximation methods, namely the BiqMac and BiqBin solvers, by comparing the CPU time and the number of function calls. The primary objective of this work was to enhance the scalability and computational efficiency in solving the max-cut problem, particularly for large-scale graph instances. Despite the development of numerous approximation algorithms, a persistent challenge lies in effectively handling problems with a large number of constraints. Our algorithm addresses this by integrating a novel semidefinite relaxation with a bundle-based optimization framework, achieving faster convergence and fewer function calls. These advancements mark a meaningful step forward in the efficient resolution of NP-hard combinatorial optimization problems.