Simplex Adjacency Graphs in Linear Optimization

Authors

  • Gerard Sierksma University of Groningen, Faculty of Economics, P.O. Box 800, 9700 AV Groningen, The Netherlands
  • Gert A. Tijssen University of Groningen, Faculty of Economics, P.O. Box 800, 9700 AV Groningen, The Netherlands

Keywords:

Simplex Method, Degeneracy Graphs, Linear Programming

Abstract

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

Vol. 1 No. 1 (2006)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.