A Fast Machine Learning Algorithm for the MaxCut Problem

The graph maxcut (MaxCut) problem is NP-hard. There are many local optima, and it is computationally difficult to find a high-quality solution. In this paper, we propose a fast machine learning algorithm inspired by the variation principle. First, we formulate the MaxCut problem as an Ising system. Second, we propose a novel learn-to-transition (L2T) algorithm that uses the Hamilton of this Ising system as the loss function to train an RNN-style neural network, approximating the transition distribution to the ground state. Finally, we evaluate our algorithm on well-known datasets and obtain good performance. Compared to the best-known solution for each graph instance, our L2T algorithm has a gap from -1.14% to -3.50%. For graphs of large size, our algorithm compares favorably with Gurobi [11], a state-of-the-art mathematical programming solver for optimization problems.