机器学习实验室博士生系列论坛（第十七期）——Recent Progress on Machine Learning Approaches for Combinatorial Optimization
报告人：Yang Peng (PKU)
时间：2021-10-27 15:10-16:10
地点：大阳城2138理科一号楼1513会议室&腾讯会议 761 4699 1810
Abstract: In recent years, leveraging machine learning (ML) to solve combinatorial optimization (CO) problems, such as travelling salesman problem (TSP) and mixed integer programming (MIP), has attracted wide interest, with the development of graph neural network (GNN) and deep reinforcement learning (DRL). Many traditional algorithms involve using hand-crafted heuristics, which may be suboptimal and ignore the fact that many instances encountered in practice often share a similar structure or come from a same distribution. However, ML-based approaches have the potential to construct better heuristics from data by exploiting the shared structure among instances. GNN, as the key building block, could effectively encodes the instances of almost all of CO problems. Imitation learning (IL) could help the agent to learn from the historical experience from the successful but expensive traditional algorithms, but with smaller computational cost. And RL allows the agent to behave even better than the historical experience in its policy, besides in its computational cost. In this talk, we will provide an overview of ML approaches for CO problems. Necessary background on GNN, IL and RL is provided. Some typical works will be introduced in detail, and we will focus on the common principles behind the methods.
