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

作　　者：Anqi Li Tiande Guo Congying Han Bonan Li Haoran Li 

机构地区：[1]School of Mathematical Sciences,University of Chinese Academy of Sciences,Beijing,100049,China

出　　处：《Science China Mathematics》2024年第6期1263-1286,共24页中国科学（数学）（英文版）

基　　金：supported by National Key R&D Program of China(Grant No.2021YFA1000403);National Natural Science Foundation of China(Grant No.11991022);the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA27000000);the Fundamental Research Funds for the Central Universities。

摘　　要：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 C_(n)^(m),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 method linear programming pivot rules reinforcement learning 

分 类 号：O221.1[理学—运筹学与控制论] TP18[理学—数学]