Article ID: | iaor19992621 |
Country: | Netherlands |
Volume: | 81 |
Issue: | 3 |
Start Page Number: | 349 |
End Page Number: | 372 |
Publication Date: | May 1998 |
Journal: | Mathematical Programming |
Authors: | Sierksma Gerard, Tijssen Gert A. |
This paper shows the relationship between degeneracy degrees and multiple solutions in linear programming (LP) models. The usual definition of degeneracy is restricted to vertices of a polyhedron. We introduce degeneracy for nonempty subsets of polyhedra and show that for LP-models for which the feasible region contains at least one vertex it holds that the dimension of the optimal face is equal to the degeneracy degree of the optimal face of the corresponding dual model. This result is obtained by means of the so-called Balinski–Tucker (B–T) Simplex Tableaus. Furthermore, we give a strong polynomial algorithm for constructing such a B–T Simplex Tableau when a solution in the relative interior of the optimal face is known.