A revised dual projective pivot algorithm for linear programming. (English) Zbl 1093.65062
The author investigates improvements to the dual projective pivot algorithm to solve a linear programming optimization problem. He begins by describing the formulation of the linear program followed by an overview of projective pivot algorithms. He then proposes an improvement to the existing techniques using properties of sparse rectangular LU factors. Instead of the usual simplex basis, the author introduces the notion of a pseudobasis, i.e., a submatrix consisting of linearly independent columns of the constraint matrix \(A\), in order to improve the performance.
The article concludes with an extensive computational investigation of the proposed algorithm using the publicly available Netlib set of test instances, as well as comparison with other established linear programming algorithms.
The article concludes with an extensive computational investigation of the proposed algorithm using the publicly available Netlib set of test instances, as well as comparison with other established linear programming algorithms.
Reviewer: Efstratios Rappos (London)
MSC:
65K05 | Numerical mathematical programming methods |
90C05 | Linear programming |
90C06 | Large-scale problems in mathematical programming |