首页|Enhancing cut selection through reinforcement learning

Enhancing cut selection through reinforcement learning

扫码查看
原文链接
  • 万方数据
  • 维普
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.

reinforcement learningmixed-integer linear programmingcutting plane methodcut selection

Shengchao Wang、Liang Chen、Lingfeng Niu、Yu-Hong Dai

展开 >

Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China

Research Center on Fictitious Economy and Data Science,Chinese Academy of Sciences,Beijing 100190,China

National Key R&D Program of ChinaNational Natural Science Foundation of ChinaNational Natural Science Foundation of China

2022YFB24034001199102112021001

2024

10.1007/s11425-023-2294-3

中国科学:数学(英文版)
中国科学院

中国科学:数学(英文版)

CSTPCD
影响因子：0.36
ISSN：1674-7283
年,卷(期)：2024.67(6)