On computational efficiency of the push-and-pull algorithm by Arsham et al

摘要

Arsham et al. always presented the push-and-pull algorithm for linear programming, and claimed that the algorithm is more effective and faster than the ordinary simplex algorithm. This paper first points out some inconsistent or inappropriate statements in the push-and-pull algorithm, and then makes a modification. If all possible incoming variables have already been used but the basic variable set (BVS) is incomplete, carry out the phase 1 simplex algorithm instead of declaring the infeasibility of the problem. Finally, a computer implementation is accomplished to give some indication of the performance of the push-and-pull algorithm on some standard test problems from NETLIB and MIPLIB. The computational results show that compared with the ordinary simplex algorithm, the push-and-pull algorithm always spends more executive time.