On the structure of the set bases of a degenerate point (Q795747): Difference between revisions

Consider an extreme point (EP) \(x^ 0\) of a convex polyhedron defined by a set of linear inequalities. If the basic solution corresponding to \(x^ 0\) is degenerate, \(x^ 0\) is called a degenerate EP. Corresponding to \(x^ 0\), there are several bases. We will characterize the set of all bases associated with \(x^ 0\), denoted by \(B^ 0\). The set \(B^ 0\) can be divided into two classes, (i) boundary bases and (ii) interior bases. For each \(B^ 0\), there is a corresponding undirected graph \(G^ 0\), in which there exists a tree which connects all the boundary bases. Some other properties are investigated, and open questions for further research are listed, such as the connection between the structure of \(G^ 0\) and cycling (e.g., in linear programs).