Notes on Bland’s pivoting rule
Notes on Bland’s pivoting rule
复制标题
关于布兰德旋转规则的注释
DOI：
--
复制
发表时间：
1978
期刊：
影响因子：
--
通讯作者：
V. Chvátal
中科院分区：
文献类型：
--
作者：
D. Avis;V. Chvátal
最近，R.G.Bland在单纯形法中提出了两条新的枢轴选择规则。这些优雅的规则源于布兰德对定向拟阵的研究；它们的优点是它们永远不会导致骑自行车。我们研究了第一种方法的效率。对于具有50个非负变量和50个附加不等式的随机生成问题，布兰德规则平均需要大约400次迭代；而流行的“最大系数”规则的相应数字只有100次左右。即使在高度退化的问题上，类似的行为似乎也会持续下去。在理论方面，我们分析了Bland规则在经典的Klee-Minty例子上的性能：对于具有n个非负变量和n个附加的不等式的问题，迭代次数从下到下被第n个Fibonacci数所限定。
Recently R.G. Bland proposed two new rules for pivot selection in the simplex method. These elegant rules arise from Bland’s work on oriented matroids; their virtue is that they never lead to cycling. We investigate the efficiency of the first of them. On randomly generated problems with 50 nonnegative variables and 50 additional inequalities, Bland’s rule requires about 400 iterations on the average; the corresponding figure for the popular “largest coefficient” rule is only about 100. Comparable behaviour seems to persist even on highly degenerate problems. On the theoretical side, we analyse the performance of Bland’s rule on the classical Klee-Minty examples: for problems with n nonnegative variables and n additional inequalities, the number of iterations is bounded from below by the n-th Fibonacci number.