An Affine-Scaling Pivot Algorithm for Linear Programming

Ping-Qi Pan(panpqseu.edu.cn)

Abstract: Simplex algorithms governed by some pivot rule and interior point algorithms are two diverging and competitive types of algorithms for solving linear programming problems. The former moves on the underlying polyhedron, from vertex to adjacent vertex, along edges until an optimal vertex is reached while the latter approaches an optimal point by moving across interior of the polyhedron. In this paper, we establish a pivot algorithm by incorporating the affine-scaling tactic to pivoting approaches used by Pan. It yields a sequence of interior points as well as a sequence of vertices, until reaching an optimal vertex. In our preliminary experiments with a set of Netlib test problems, a dense implementation of the proposed affine-scaling pivot algorithm outperformed the affine-scaling (interior point) algorithm significantly, with total iteration and time ratio 4:56 and 1:52, respectively.

Keywords: pivot, interior point, affine-scaling, orthogonal factorization

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

Citation: Department of Mathematics, Southest University, 210096, China

Download: [PDF]

Entry Submitted: 10/17/2007
Entry Accepted: 10/17/2007
Entry Last Modified: 10/17/2007

Modify/Update this entry