Simplex Adjacency Graphs in Linear Optimization
Keywords:
Simplex Method, Degeneracy Graphs, Linear ProgrammingAbstract
Simplex Adjacency graphs represent the possible Simplex pivot operations (the edges) between pairs of feasible bases (the nodes) of linear optimization models. These graphs are mainly studied so far in the context of degeneracy. The more general point of view in this paper leads to a number of new results, mainly concerning the connectivity and the feasibility-optimality duality in these graphs. Among others, we present a very short proof of a result of P. Zörnig and T. Gall (1996) on the connectivity of subgraphs corresponding to optimal vertices, and we answer H.-J. Kruse’s (1993) question on the connectivity of graphs related to the negative pivots in optimal vertices.Downloads
Published
2006-01-24
How to Cite
Sierksma, G., & Tijssen, G. A. (2006). Simplex Adjacency Graphs in Linear Optimization. Algorithmic Operations Research, 1(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/96
Issue
Section
Articles