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

Authors: Shuyun Li; Huan Ma; Zhihui Wang; Xinchang Zhang

Addresses: Department of Computer Science and Technology, Qilu University of Technology (Shandong Academy of Sciences), Jinan, 250353, China ' Department of Computer Science and Technology, Qilu University of Technology (Shandong Academy of Sciences), Jinan, 250353, China ' Department of Computer Science and Technology, Qilu University of Technology (Shandong Academy of Sciences), Jinan, 250353, China ' Department of Information Science and Engineering, Shandong Normal University, Jinan, 250358, China

Abstract: 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.

Keywords: NP-hard problems; review; machine learning; combinatorial optimisation; deep reinforcement learning; travelling salesman problem; bin packing problem; virtual network embedding problem.

DOI: 10.1504/IJCSM.2025.149631

International Journal of Computing Science and Mathematics, 2025 Vol.22 No.1, pp.1 - 31

Received: 21 Mar 2024
Accepted: 21 May 2025
Published online: 07 Nov 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article