Solving Combinatorial Optimization Problems with Deep Neural Network:A Survey  

作　　者：Feng Wang Qi He Shicheng Li 

机构地区：[1]School of Computer Science,Wuhan University,Wuhan 430072,China

出　　处：《Tsinghua Science and Technology》2024年第5期1266-1282,共17页清华大学学报自然科学版（英文版）

基　　金：supported by the National Natural Science Foundation of China(Nos.62173258 and 61773296).

摘　　要：Combinatorial Optimization Problems(COPs)are a class of optimization problems that are commonly encountered in industrial production and everyday life.Over the last few decades,traditional algorithms,such as exact algorithms,approximate algorithms,and heuristic algorithms,have been proposed to solve COPs.However,as COPs in the real world become more complex,traditional algorithms struggle to generate optimal solutions in a limited amount of time.Since Deep Neural Networks(DNNs)are not heavily dependent on expert knowledge and are adequately flexible for generalization to various COPs,several DNN-based algorithms have been proposed in the last ten years for solving COPs.Herein,we categorize these algorithms into four classes and provide a brief overview of their applications in real-world problems.

关 键 词：Combinatorial Optimization Problem(COPs) pointer network Transformer Graph Neural Network(GNN) Reinforcement Learning(RL) 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程] TP391.41[自动化与计算机技术—控制科学与工程]