检索结果-南通市图书馆

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

Science China Mathematics 2024年第6期67卷 1263-1286页

作者： Anqi Li Tiande Guo Congying Han Bonan Li Haoran Li School of Mathematical Sciences University of Chinese Academy of SciencesBeijing100049China

Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst ***,the optimal pivot of the simplex method is *** 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 ***,we first propose the SimplexPseudoTree to transfer the simplex method into tree search mode while avoiding repeated basis ***,we propose four reinforcement learning models with two actions and two rewards to make the Monte Carlo tree search suitable for the simplex ***,we set a new action selection criterion to ameliorate the inaccurate evaluation in the initial *** 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 *** addition,we experimentally validate that the proposed schedule can avoid unnecessary search and provide the optimal pivot ***,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

来源：

维普期刊数据库

同方期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

New Optimal pivot Rule for the Simplex Algorithm

引用

Advances in Pure Mathematics 2016年第10期6卷 647-658页

作者： Jean Bosco Etoa Etoa Department of Economic and Management Sciences University of Yaounde II Soa Cameroon

The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). One of the important steps of the simplex algorithm is applying an appropriate pivot rule to select the basis-entering variable corresponding to the maximum reduced cost. Unfortunately, this pivot rule not only can lead to a critical cycling (solved by Bland’s rules), but does not improve efficiently the objective function. Our new pivot rule 1) solves the cycling problem in the original Dantzig’s simplex pivot rule, and 2) leads to an optimal improvement of the objective function at each iteration. The new pivot rule can lead to the optimal solution of LP with a lower number of iterations. In a maximization problem, Dantzig’s pivot rule selects a basis-entering variable corresponding to the most positive reduced cost;in some problems, it is well-known that Dantzig’s pivot rule, before reaching the optimal solution, may visit a large number of extreme points. Our goal is to improve the simplex algorithm so that the number of extreme points to visit is reduced;we propose an optimal improvement in the objective value per unit step of the basis-entering variable. In this paper, we propose a pivot rule that can reduce the number of such iterations over the Dantzig’s pivot rule and prevent cycling in the simplex algorithm. The idea is to have the maximum improvement in the objective value function: from the set of basis-entering variables with positive reduced cost, the efficient basis-entering variable corresponds to an optimal improvement of the objective function. Using computational complexity arguments and some examples, we prove that our optimal pivot rule is very effective and solves the cycling problem in LP. We test and compare the efficiency of this new pivot rule with Dantzig’s original pivot rule and the simplex algorithm in MATLAB environment.

关键词： Linear Programming Simplex Algorithm pivot rules Optimal pivot Rule

来源：

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：