Enhancing cut selection through reinforcement learning

作     者：Shengchao Wang Liang Chen Lingfeng Niu Yu-Hong Dai 

作者机构：Academy of Mathematics and Systems ScienceChinese Academy of SciencesBeijing100190China Research Center on Fictitious Economy and Data ScienceChinese Academy of SciencesBeijing100190China 

出 版 物：《Science China Mathematics》 (中国科学（数学）（英文版）)

年 卷 期：2024年第67卷第6期

页      面：1377-1394页

核心收录：

学科分类：07[理学] 08[工学] 081104[工学-模式识别与智能系统] 070105[理学-运筹学与控制论] 0811[工学-控制科学与工程] 0701[理学-数学] 

基　　金：supported by the National Key R&D Program of China(Grant No.2022YFB2403400) National Natural Science Foundation of China(Grant Nos.11991021 and 12021001)。 

主　　题：reinforcement learning mixed-integer linear programming cutting plane method cut selection 

摘      要：With the rapid development of artificial intelligence in recent years,applying various learning techniques to solve mixed-integer linear programming(MILP)problems has emerged as a burgeoning research domain.Apart from constructing end-to-end models directly,integrating learning approaches with some modules in the traditional methods for solving MILPs is also a promising direction.The cutting plane method is one of the fundamental algorithms used in modern MILP solvers,and the selection of appropriate cuts from the candidate cuts subset is crucial for enhancing efficiency.Due to the reliance on expert knowledge and problem-specific heuristics,classical cut selection methods are not always transferable and often limit the scalability and generalizability of the cutting plane method.To provide a more efficient and generalizable strategy,we propose a reinforcement learning(RL)framework to enhance cut selection in the solving process of MILPs.Firstly,we design feature vectors to incorporate the inherent properties of MILP and computational information from the solver and represent MILP instances as bipartite graphs.Secondly,we choose the weighted metrics to approximate the proximity of feasible solutions to the convex hull and utilize the learning method to determine the weights assigned to each metric.Thirdly,a graph convolutional neural network is adopted with a self-attention mechanism to predict the value of weighting factors.Finally,we transform the cut selection process into a Markov decision process and utilize RL method to train the model.Extensive experiments are conducted based on a leading open-source MILP solver SCIP.Results on both general and specific datasets validate the effectiveness and efficiency of our proposed approach.