  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. This study proposes the optimal rule to find all shortest
pivot paths of the simplex method for linear programming problems based on
Monte Carlo tree search (MCTS). 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 (RL) 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.
