On the structure of the set bases of a degenerate point
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).
- A general method for determining the set of all efficient solutions to a linear vectormaximum problem
- A network simplex method
- An Algorithm for Finding All Vertices of Convex Polyhedral Sets
- Finding all vertices of a convex polyhedron
- Generating all maximal efficient faces for multiple objective linear programs
- scientific article; zbMATH DE number 3634009 (Why is no real title available?)
- scientific article; zbMATH DE number 3397316 (Why is no real title available?)
- Linear multiobjective programming
- Linear Multiparametric Programming by Multicriteria Simplex Method
- Multiparametric Linear Programming
- New Finite Pivoting Rules for the Simplex Method
- On cycling in the network simplex method
- Optimality and Degeneracy in Linear Programming
- The Enumeration of the Set of All Efficient Solutions for a Linear Multiple Objective Program
- Shadow prices and sensitivity analysis in linear programming under degeneracy. State-of-the-art-survey
- Survey of solved and open problems in the degeneracy phenomenon
- A new pivoting rule for solving various degeneracy problems
- Weakly redundant constraints and their impact on postoptimal analyses in LP
- On the connectedness of optimum-degeneracy graphs
- Selected bibliography on degeneracy
- Degeneracy graphs: Theory and applications. An updated survey
- Bounds on the number of vertices of perturbed polyhedra
- On degeneracy and collapsing in the construction of the set of objective values in a multiple objective linear program
- An improved \(N\)-tree algorithm for the enumeration of all neighbors of a degenerate vertex
- On some properties of \(0\)-degeneracy graphs
- A theory of degeneracy graphs
- Finding all maximal efficient faces in multiobjective linear programming
- Enumerating extreme points of a highly degenerate polytope
- Determination of the efficient set in multiobjective linear programming
- Practical issues on the projection of polyhedral sets
- On the line graphs of the complete r-partite graphs
- Degeneracy subgraph of the Lemke complementary pivot algorithm and anticycling rule
- Fourier algorithm revisited
This page was built for publication: On the structure of the set bases of a degenerate point
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795747)
