Balinski–Tucker Simplex Tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces

Balinski–Tucker Simplex Tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces

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

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.

Reviews

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