A simple direct cosine simplex algorithm

摘要

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.