  


An AffineScaling Pivot Algorithm for Linear Programming
PingQi 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 affinescaling 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 affinescaling pivot algorithm outperformed the affinescaling (interior point) algorithm significantly, with total iteration and time ratio 4:56 and 1:52, respectively. Keywords: pivot, interior point, affinescaling, orthogonal factorization Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Department of Mathematics, Southest University, 210096, China Download: Entry Submitted: 10/17/2007 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  