A modified version of the Edmonds-Fukuda algorithm for LP problems in the general form

A modified version of the Edmonds-Fukuda algorithm for LP problems in the general form

0.00 Avg rating0 Votes
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:
Keywords: duality
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.