Dual Face Algorithm for Linear Programming

Ping-Qi Pan (panpqseu.edu.cn)

Abstract: The proposed algorithm proceeds from dual face to dual face, until reaching a dual optimal face along with a pair of dual and primal optimal solutions, compared with the simplex algorithm, which moves from vertex to vertex. It computes the search direction as an orthogonal projection of the dual objective gradient onto a relevant null space. In each iteration, it solves a single small triangular system, compared with four triangular systems handled by the simplex algorithm. We report preliminary but favorable computational results with a set of standard Netlib test problems.

Keywords: linear programming, dual level face, dual optimal face, Cholesky factorization, orthogonal projection

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Department of Mathematics, Southeast University, 210096, China, 6/2009

Download: [PDF]

Entry Submitted: 10/17/2007
Entry Accepted: 10/17/2007
Entry Last Modified: 06/11/2009

Modify/Update this entry