Ping-Qi Pan The dual face algorithm for linear programming (LP) was proposed by the author in 2014. Using QR factorization, it proceeds from dual face to dual face, until reaching an optimal dual face along with dual and primal optimal solutions, unless detecting infeasibility of the problem. On the other hand, a variant of the algorithm using … Read more
The unique feature of the face algorithm \cite{pan14} is that it moves from face to face, rather than from vertex to vertex as the simplex algorithm. It uses the orthogonal projection of the negative objective gradient on the related null space as its search direction. Nevertheless, the algorithm is based on QR factorization, which would … Read more
An attractive feature of the face method \cite{pan14} for solving LP problems is that it uses the orthogonal projection of the negative objective gradient on the related null space as the search direction. However, the method would not be amenable for solving large sparse problems, since it handles the involved normal system by orthogonal transformations. … Read more
The dual face algorithm uses Cholesky factorization, as would be not very suitable for sparse computations. The purpose of this paper is to present a dual face algorithm using Gauss-Jordan elimination for solving bounded-variable LP problems. ArticleDownload View PDF
Zhang et al recently propose another approach to the face algorithm. This note gives a modification of the result. ArticleDownload View PDF
As a natural extension of the dual simplex algorithm, the dual face algorithm performed remarkably in computational experiments with a set of Netlib standard problems. In this paper, we generalize it to bounded-variable LP problems via local duality. CitationDepartment of Mathematics, Southeast University, Nanjing, 210096, China, 12/2014ArticleDownload View PDF
The simplex algorithm travels, on the underlying polyhedron, from vertex to vertex until reaching an optimal vertex. With the same simplex framework, the proposed algorithm generates a series of feasible points (which are not necessarily vertices). In particular, it is exactly an interior point algorithm if the initial point used is interior. Computational experiments show … Read more