A basis-deficiency-allowing primal phase-I algorithm using the most-obtuse-angle column rule. (English) Zbl 1178.90247
Summary: The dual Phase-1 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.
References:
| [1] | Pan, P.-Q., New non-monotone procedures for achieving dual feasibility, Journal of Nanjing University Mathematical Biquarterly, 12, 2, 155-162 (1995), November · Zbl 0844.90055 |
| [2] | Pan, P.-Q., The most-obtuse-angle row pivot rule for achieving dual feasibility: A computational study, Europ. J. Operl. Res., 101, 1, 167-176 (1997), August · Zbl 0921.90119 |
| [3] | Pan, P.-Q., A dual projective simplex method for linear programming, Computers Math. Applic., 35, 119-135 (1998), 6 · Zbl 0907.90208 |
| [4] | Pan, P.-Q., A basis-deficiency-allowing variation of the simplex method for linear programming, Computers Math. Applic., 36, 3, 33-53 (1998), August · Zbl 0941.90055 |
| [5] | Pan, P.-Q.; Pan, Y.-P., A Phase-1 approach for the generalized simplex algorithm, Computers Math. Applic., 42, 10/11, 1455-1464 (2001), November · Zbl 1002.90036 |
| [6] | Pan, P.-Q.; Li, W.; Wang, Y., A Phase-I algorithm using the most-obtuse-angle rule for the basis-deficiency-allowing dual simplex method, OR Transactions, 8, 3, 88-96 (2004), (in Chinese) |
| [7] | Santos-Palomo, A., The sagitta method for solving linear programs, Europ. J. Operl. Res., 157, 3, 527-539 (2004), September · Zbl 1067.90123 |
| [8] | Guerrero-Garcia, P., Range-Space Methods for Sparse Linear Programs, (Ph.D. Thesis (2000), Department of Applied Mathematics, University of Málaga: Department of Applied Mathematics, University of Málaga Spain), July |
| [9] | Coleman, T.; Branch, M. A.; Grace, A., Optimization Toolbox v2.1 for use with MATLAB, user’s guide, (Technical Report (1999), The Math Works Inc.) |
| [10] | HolmstrΩ, K., The TOMLAB optimization environment v3.0 user’s guide, (Technical Report (2001), Mälardalen University: Mälardalen University Sweden), April |
| [11] | Guerrero-García, P.; Santos-Palomo, Á., Phase-I cycling under the most-obtuse-angle pivot rule, Europ. J. Operl. Res., 167, 1, 20-27 (2005), November · Zbl 1074.90026 |
| [12] | Pan, P.-Q., Practical finite pivoting rules for the simplex method, OR Spektrum, 12, 219-225 (1990) · Zbl 0714.90063 |
| [13] | Guerrero-García, P.; Santos-, Á., Palomo A non-simplex active-set framework for basis-deficiency-allowing simplex variations, (D., Griffiths; G. A., Watson, Proceedings of the \(20^{th}\) Biennial Conference on Numerical Analysis (2003), Dundee: Dundee Scotland), 19, June |
| [14] | Santos-Palomo, Á.; Guerrero-García, P., Sagitta method with guaranteed convergence, (Technical Report (2005), Department of Applied Mathematics, University of Málaga), February |
| [15] | Bjck, Å., Numerical Methods for Least Squares Problems (1996), SIAM Pubs.: SIAM Pubs. Philadelphia, PA · Zbl 0847.65023 |
| [16] | Santos-Palomo, Á.; Guerrero-García, P., Computational experiences with dense and sparse implementations of the sagitta method, (Technical Report (2005), Department of Applied Mathematics, University of Malaga), February |
| [17] | Gay, D. M., Electronic mail distribution of linear programming test problems, Committee on Algorithms (COAL) Newsletter, 13, 10-12 (1985) |
| [18] | Guerrero-García, P.; Santos-Palomo, Á., A comparison of three sparse linear program solvers, (Technical Report (2003), Department of Applied Mathematics, University of Málaga), October |
| [19] | Bjck, Å., A direct method for sparse least squares problems with lower and upper bounds, Numer. Math., 54, 19-32 (1988) · Zbl 0659.65039 |
| [20] | Oreborn, U., A Direct Method for Sparse Nonnegative Least Squares Problems, (Licentiat thesis (1986), Department of Mathematics: Department of Mathematics Linköping University, Sweden) |
| [21] | Santos-Palomo, Á.; Guerrero-García, P., Solving a sequence of sparse least squares problems, (Technical Report (2001), Department of Applied Mathematics, University of Malaga), September |
| [22] | Coleman, T. F.; Hulbert, L. A., A direct active set algorithm for large sparse quadratic programs with simple lower bounds, Math. Progr., 45, 373-406 (1989) · Zbl 0691.90070 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
