中心在2019年就开始着手基于学习的组合优化研究，中心在该领域的研究可分为两种，其一是基于传统学习方法如表格强化学习、可满足性问题中的子句学习等；另一种是基于深度学习如图神经网络、深度强化学习等。所提出的结合强化学习、图神经网络的算法在旅行商、最大可满足性、最大公共子图、大规模车间调度等多个经典组合优化问题上超过了现有的优化算法。相关成果发表于AAAI、IJCAI、SIGKDD等各类人工智能与数据挖掘顶级会议上。结合子句学习与分支定界算法求解MaxSAT的论文获得了约束规划原理与实践国际会议(CP 2021)的最佳论文奖。

代表性论文成果：

基于传统学习：

[1] Yan-Li Liu#, Chu-Min Li#, Hua Jiang*, Kun He*. A Learning based Branch and Bound for Maximum Common Subgraph Related Problems. The 34th AAAI Conference on Artificial Intelligence, AAAI (Oral) 2020: 2392-2399.

[2] Jiongzhi Zheng, Kun He*, Jianrong Zhou, Yan Jin, Chu-Min Li. Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem. AAAI 2021: 12445-12452.

[3] Jiongzhi Zheng, Kun He*, Jianrong Zhou, Yan Jin, Chu-Min Li, Felip Manya. BandMaxSAT. Multi-armed Bandit for the Local Search MaxSAT Solver. IJCAI 2022: 1901-1907.

[4] Jianrong Zhou, Kun He*, Jiongzhi Zheng, Chu-Min Li, Yanli Liu. A Strengthened Branch and Bound Algorithm for the Maximum Common Subgraph Problems. IJCAI 2022: 1908-1914.

[5] Jiongzhi Zheng, Kun He*, Jianrong Zhou. Farsighted Probabilistic Sampling: A General Strategy for Boosting Local Search MaxSAT Solvers. AAAI 2023.

[6] Yanli Liu, Jiming Zhao, Chu-Min Li*, Hua Jiang, Kun He. Hybrid Learning with New Value Function for the Maximum Common Subgraph Problem.

[7] Jiongzhi Zheng, Kun He*, Jianrong Zhou, Yan Jin, Chu-Min Li. Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems. Knowledge-Based Systems (KBS), to appear (2022).

[8] Chu-Min Li, Zhenxing Xu, Jordi Coll, Felip Manyà, Djamal Habet, Kun He. Combining Clause Learning and Branch and Bound for MaxSAT. CP 2021: 38:1-38:18. (Best Paper Award)

基于深度学习：

[1] Fei Ni, Jianye Hao*, Jiawen Lu, Xialiang Tong, Jiahui Duan, Yi Ma, Kun He*. A Multi-Graph Attributed Reinforcement Learning based Optimization Algorithm for Large-scale Hybrid Flow Shop Scheduling Problem. KDD 2021: 3441-3451.

[2] Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He*, Li Zhao, Tao Qin, Lei Song, Jiang Bian. Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem. AAAI 2023.

[3] Xuanhao Pan, Yan Jin, et al. H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem. AAAI 2023.

代表性竞赛成果：

1、2022 SAT可满足性问题国际算法竞赛主赛道冠军；

2、2022 MaxSAT最大可满足性问题国际算法竞赛四个赛道中三个亚军、一个季军；

3、2022第12届DIMACS算法挑战赛CVRP赛道第七名。