A note on the Edmonds-Fukuda pivoting rule for simplex algorithms

DOI10.1016/0377-2217(87)90251-7MaRDI QIDQ1095028zbMATH OpenOpenAlexFDO

Authors Jens Clausen

Publication date 1987

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(87)90251-7

zbMATH Keywords

cyclingpivot rule of Edmonds-Fukudasimplex algorithmsstalling

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Review text

The pivot rule of Edmonds-Fukuda for simplex algorithms is discussed. A proof is given that this rule maintains feasibility of the solution during the solution process. The relation to the recursive ``rule II- method of \textit{R. G. Bland} [Math. Oper. Res. 2, 103-107 (1977; Zbl 0408.90050)] is discussed. As the author remarks this pivoting rule (presumably) is not so effective as the classical Dantzig pivoting rule for non-degenerate problems.

Recommendations

• scientific article; zbMATH DE number 3904322
• scientific article; zbMATH DE number 1960976
• Practical finite pivoting rules for the simplex method
• On the complexity of a pivot step of the revised simplex algorithm
• On anti-cycling pivoting rules for the simplex method
• Simplicial pivoting algorithms for a tractable class of integer programs
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• scientific article; zbMATH DE number 14316
• A largest-distance pivot rule for the simplex algorithm
• The simplex algorithm with a new primal and dual pivot rule

Cites work

• A new polynomial-time algorithm for linear programming
• scientific article; zbMATH DE number 3825556 (Why is no real title available?)
• scientific article; zbMATH DE number 3626518 (Why is no real title available?)
• New Finite Pivoting Rules for the Simplex Method

Cited in

(7)

• Pivot rules for linear programming: A survey on recent theoretical developments
• An exterior point simplex algorithm for (general) linear programming problems
• Criss-cross methods: A fresh view on pivot algorithms
• scientific article; zbMATH DE number 4045475 (Why is no real title available?)
• scientific article; zbMATH DE number 179276 (Why is no real title available?)
• A comprehensive simplex-like algorithm for network optimization and perturbation analysis
• On Simplex Pivoting Rules and Complexity Theory

This page was built for publication: A note on the Edmonds-Fukuda pivoting rule for simplex algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095028)