Degeneracy graphs and simplex cycling (Q1189552)

This book investigates degeneracy issues of linear inequality systems. The problem is studied by means of degeneracy graphs. The vertices of these graphs correspond to bases describing the same (degenerate) solution. Two vertices are connected by an edge, if the corresponding bases can mutually by obtained by one pivot operation (with a positive or negative pivot element). Several graph theoretical properties of degeneracy graphs are proved, e.g. concerning their diameter and connectivity. In particular, degeneracy graphs stemming from basic solutions with two basic zero- variables are analyzed. Then necessary and sufficient conditions on the coefficient matrix for the occurrence of simplex cycling are investigated. This question is approached in three ways: by degeneracy graphs, by geometric arguments and by means of determinants. It is shown that a simplex cycle relates uniquely to certain inequalities of determinants. These properties are taken to construct cycling examples. The book closes with extensive references on degeneracy and cycling issues.