期刊文献+

二次检索

题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

年份

作者

机构

共找到4篇文章
< 1 >
每页显示 20 50 100
New Optimal Pivot Rule for the Simplex Algorithm
1
作者 Jean Bosco Etoa Etoa 《Advances in Pure Mathematics》 2016年第10期647-658,共12页
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). O... 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
下载PDF
A non-monotone Phase-1 method in linear programming 被引量:4
2
作者 潘平奇 李炜 《Journal of Southeast University(English Edition)》 EI CAS 2003年第3期293-296,共4页
To gain superior computational efficiency, it might be necessary to change the underlying philosophy of the simplex method. In this paper, we propose a Phase-1 method along this line. We relax not only the conventiona... To gain superior computational efficiency, it might be necessary to change the underlying philosophy of the simplex method. In this paper, we propose a Phase-1 method along this line. We relax not only the conventional condition that some function value increases monotonically, but also the condition that all feasible variables remain feasible after basis change in Phase-1. That is, taking a purely combinatorial approach to achieving feasibility. This enables us to get rid of ratio test in pivoting, reducing computational cost per iteration to a large extent. Numerical results on a group of problems are encouraging. 展开更多
关键词 linear programming Phase-1 ratio-test-free pivoting rule
下载PDF
Optimal pivot path of the simplex method for linear programming based on reinforcement learning 被引量:1
3
作者 Anqi Li Tiande Guo +2 位作者 Congying Han Bonan Li Haoran Li 《Science China Mathematics》 SCIE CSCD 2024年第6期1263-1286,共24页
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... 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
原文传递
A FAST SIMPLEX ALGORITHM FOR LINEAR PROGRAMMING 被引量:3
4
作者 Pingqi Pan 《Journal of Computational Mathematics》 SCIE CSCD 2010年第6期837-847,共11页
Recently, computational results demonstrated remarkable superiority of a so-called "largest-distance" rule and "nested pricing" rule to other major rules commonly used in practice, such as Dantzig's original rule... Recently, computational results demonstrated remarkable superiority of a so-called "largest-distance" rule and "nested pricing" rule to other major rules commonly used in practice, such as Dantzig's original rule, the steepest-edge rule and Devex rule. Our computational experiments show that the simplex algorithm using a combination of these rules turned out to be even more efficient. 展开更多
关键词 Large-scale linear programming Simplex algorithm Pivot rule Nested Largestdistance Scaling.
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部