A basis-deficiency-allowing primal phase-1 algorithm using the most-obtuse-angle column rule
The dual Phase-I algorithm using the most-obtuse-angle row pivot rule is very efficient for providing a dual feasible basis, in either the classical or the basis-deficiency-allowing context. In this paper, we establish a basis-deficiency-allowing Phase-I algorithm using the so-called most-obtuse-angle column pivot rule to produce a primal (deficient or full) basis. Our computational experiments with the smallest test problems from the standard NETLIB set show that a dense projected-gradient implementation largely outperforms that of the variation of the primal simplex method from the commercial code MATLAB LINPROG V1.17, and that a sparse projected-gradient implementation of a normalized revised version of the proposed algorithm runs 34% faster than the sparse implementation of the primal simplex method included in the commercial code TOMLAB LPSOLVE v3.0. (C) 2006 Elsevier Ltd. All rights reserved.
pivoting rule simplex method deficient basis most-obtuse-angle rule