Article ID: | iaor19941912 |
Country: | Singapore |
Volume: | 8 |
Issue: | 1 |
Start Page Number: | 55 |
End Page Number: | 61 |
Publication Date: | May 1991 |
Journal: | Asia-Pacific Journal of Operational Research |
Authors: | Wang Zhemin |
Keywords: | duality |
The Edmonds-Fukuda algorithm is a pivot algorithm devised originally for oriented matroid programming that happens to be a combinatorial setting of linear programming. This algorithm does not maintain feasibility in general but it does for LP problems in particular. It can be applied only to LP problems in the standard form, and it needs a stack in addition. The paper proposes a modified version of this algorithm for LP problems in the general form that maintains feasibility and needs no stack. This algorithm also outputs an upper bounded integer that increases (not only by one unit in general) at each iteration, no matter whether degeneracy occurs or not.