A survey of machine learning approaches to solving NP-hard problems

NP-hard problems have attracted considerable attention due to their computational complexity and widespread practical applications. Traditional algorithms often struggle to handle large-scale instances of these problems due to their exponential time complexity. In recent years, machine learning (ML) methods have emerged as effective tools for solving NP-hard problems, leveraging their powerful pattern recognition capabilities, adaptability, and generalisation abilities. However, different types of NP-hard problems are suited to different ML methods, and there are significant differences in solving capabilities between ML methods and traditional algorithms. This paper systematically reviews the latest advancements in applying ML to the traveling salesman problem (TSP), bin packing problem (BPP), and Virtual Network Embedding Problem. It also compares the strengths and weaknesses of ML methods versus traditional algorithms in terms of algorithmic performance, computational complexity, and applicability. Finally, the paper analyses the key challenges faced by ML methods in solving NP-hard problems and outlines future research directions, aiming to provide a reference for subsequent research.