An efficient search direction for linear programming problems

In this paper. we present an auxiliary algorithm, in terms of the speed of obtaining the optimal solution, that is effective in helping the simplex me thod for commencing a better initial basic feasible solution. The idea of c hoosing a direction towards an optimal point presented in this paper is new and easily implemented. From our experiments, the algorithm will release a corner point of the feasible region within few iterative steps, independen t of the starting point. The computational results show that after the auxi liary algorithm is adopted as phase I process, the simplex method consisten tly reduce the number of required iterations by about 40%. Scope and purpose Recent progress in the implementations of simplex and interior point method s as well as advances in computer hardware has extended the capability of l inear programming with today's computing technology. It is well known that the solution times for the interior point method improve with problem size. But, experimental evidence suggests that interior point methods dominate s implex-based methods only in the solution of very large scale linear progra ms. If the problem size is medium, how to combine the best features of thes e two methods to produce an effective algorithm for solving linear programm ing problems is still an interesting problem. In this research we present a new effective epsilon -optimality search direction based on the interior p oint method to start an initial basic feasible solution near the optimal po int for the simplex method. (C) 2001 Elsevier Science Ltd. All rights reser ved.