Optimal pivot path of the simplex method for linear programming based on reinforcement learning

扫码查看

原文链接

万方数据
维普

外文摘要：Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to find all the shortest pivot paths of the simplex method for linear programming problems based on Monte Carlo tree search.Specifically,we first propose the SimplexPseudoTree to transfer the simplex method into tree search mode while avoiding repeated basis variables.Secondly,we propose four reinforcement learning models with two actions and two rewards to make the Monte Carlo tree search suitable for the simplex method.Thirdly,we set a new action selection criterion to ameliorate the inaccurate evaluation in the initial exploration.It is proved that when the number of vertices in the feasible region is Cnm,our method can generate all the shortest pivot paths,which is the polynomial of the number of variables.In addition,we experimentally validate that the proposed schedule can avoid unnecessary search and provide the optimal pivot path.Furthermore,this method can provide the best pivot labels for all kinds of supervised learning methods to solve linear programming problems.

外文关键词：

simplex methodlinear programmingpivot rulesreinforcement learning

作者：

Anqi Li、Tiande Guo、Congying Han、Bonan Li、Haoran Li

展开 >

作者单位：

School of Mathematical Sciences,University of Chinese Academy of Sciences,Beijing 100049,China

基金：

National Key R&D Program of ChinaNational Natural Science Foundation of ChinaStrategic Priority Research Program of Chinese Academy of SciencesFundamental Research Funds for the Central Universities

项目编号：

2021YFA100040311991022XDA27000000

出版年：

2024

DOI：

10.1007/s11425-022-2259-1

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

中国科学院

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

CSTPCD

影响因子：0.36

ISSN：1674-7283

年,卷(期)：2024.67(6)