Optimization Online


An Affine-Scaling Pivot Algorithm for Linear Programming

Ping-Qi Pan (panpq***at***seu.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


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society