An extreme-point-ranking algorithm for the extreme-point mathematical programming problem (Q580171)

Consider the extreme-point mathematical programming problem (EPMP): maximize cx subject to \(x\in X\cap V\), where \(X=\{x\in R^ n:\) Ax\(\leq b\}\) and V is the set of vertices of the polytope \(Y=\{x\in R^ n:\) Dx\(\leq f\), \(x\geq 0\}\). The algorithms for solving EPMP are of three basic types, namely, extreme-point ranking, branch and bound and cutting-plane types of algorithms. The authors propose a more efficient variant of the extreme-point ranking type of algorithms, discuss implementation details and give computational experience for the proposed algorithm. The implementation details described for the algorithm also yield as a by- product an efficient way of finding all alternative optimal solutions to a linear programming problem and a method for ranking all vertices of a polytope with a controlled storage requirement.