Degeneracy graph

From Glossary

Jump to: navigation, search

An undirected graph, where the nodes represent bases and edges their adjacency. The degeneracy graph is a way to probe deeply into a degenerate extreme point (represented by more than one basic feasible solution). Among other things, it reveals good pivot steps through the point enroute to an optimum, and it provides a clear, efficient approach to sensitivity analysis.

  • Here are some terms for a degeneracy graph associated with a (basic) solution, LaTeX: x:
  • degeneracy power of LaTeX: x: number of bases corresponding to LaTeX: x.
  • internal node: a node whose neighbors are all in this degeneracy graph.
  • transition column: a tableau column such that a pivot exists for which that column enters the basis, and the new basis corresponds to a transition node.
  • transition node: a node with at least one member outside this degeneracy graph (so a pivot moves to a different solution).
  • Transition Node Pivoting(TNP) rule: a lexicographic rule using a special column to avoid internal nodes (but cycling is possible).

Personal tools