×

A simple direct cosine simplex algorithm. (English) Zbl 1169.65061

Summary: Linear programming (LP) is the core model of constrained optimization. The simplex method (simplex in short) has been proven in practice to perform very well in small- or medium-sized LP problems. A new algorithm called the direct cosine simplex algorithm (DCA) is presented here to improve upon simplex and to solve LP problems. The proposed DCA implements a specific cosine criterion to choose the entering variable instead of the traditional most negative rule used in simplex.
Three examples are given to illustrate the implementation of the proposed DCA to improve simplex and to serve as the optimization tool. The utility of the proposed approach is evident from the extensive computational results on test problems adapted from NETLIB. DCA reduced the number of iterations of simplex in most cases in our computational experiment. Preliminary results for medium-sized problems are encouraging.

MSC:

65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dantzig, G. B., Maximization of a linear function of variables subject to linear inequalities, (Koopmans, T. C., Activity Analysis of production and Allocation (1951), John Wiley: John Wiley NY), 339-347
[2] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ · Zbl 0108.33103
[3] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065
[4] Vanderbei, R., Interior-point methods: algorithms and formulations, ORSA J. Comput., 6, 32-34, 331 (1994)
[5] Gill, P. E.; Murray, W.; Wright, M. H., Practical Optimization (1981), Academic Press: Academic Press NY · Zbl 0503.90062
[6] Hiller, F. S.; Lieberman, G. J., Introduction to Operations Research (1995), McGraw-Hill: McGraw-Hill NY · Zbl 0155.28202
[7] Vanderbei, R., Linear Programming: Foundations and Extensions (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 1043.90002
[8] Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D., Linear Programming and Network Flows (2004), John Wiley: John Wiley NY
[9] Klee, V.; Minty, G., How good is the simplex algorithm?, (Shisha, O., Inequalities-III (1972), Academic Press: Academic Press NY), 159-175
[10] Naylor, B.; Sell, G., Linear Operator Theory in Engineering and Science (1982), Springer-Verlag: Springer-Verlag NY
[11] Trigos, F.; Frausto-Solis, J.; Lopez, RR., A simplex cosine method for solving the Klee-Minty cube, Advances in Simulation System Theory and Systems Engineering, 70X, 27-32 (2002)
[12] M.M. Murshod, B.M. Sarwar, M.A. Sattar, M. Kaykobad, A New Polynomial Algorithm for Linear Programming Problem, NEC Research Institute, 1993.; M.M. Murshod, B.M. Sarwar, M.A. Sattar, M. Kaykobad, A New Polynomial Algorithm for Linear Programming Problem, NEC Research Institute, 1993.
[13] Stojkovic, N. V.; Stanimirovic, P. S., Two direct methods in linear programming, Eur. J. Oper. Res., 131, 417-439 (2001) · Zbl 0991.90087
[14] Junior, H. V.; Lins, M. P.E., An improved initial basis for the simplex algorithm, Comput. Oper. Res., 32, 1983-1993 (2005) · Zbl 1068.90079
[15] Corley, H. W.; Rosenberger, J.; Yeh, W.-C.; Sung, T. K., The cosine simplex algorithm, Int. J. Adv. Manuf. Technol., 27, 1047-1050 (2006)
[16] Bland, R., New finite pivoting rules for the simplex method, Math. Oper. Res., 2, 103-107 (1977) · Zbl 0408.90050
[17] <http://www.netlib.org/lp/data>; <http://www.netlib.org/lp/data>
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.