The feasibility problem in the simplex algorithm

Abstract

The simplex method is one way of solving a linear programming problem (LP-problem). The simplex method needs a basic feasible solution to start the solution process. This requires an available non-singular basis. Normally it is difficult to identify a non-sin!,rular basis from the problem data. Thus the simplex method introduces the concept of artificial variables that provides a non-singular basis. An artificial objective function is also introduced in such a way that the cost coefficients of the artificial variables are positive (negative), while the cost coefficients of the other variables are zero. By minimizing (maximizing) this new objective function, with the simplex algorithm, a feasible solution for the original problem is obtained. This is also known as the phase one problem of the simplex algorithm. Our paper will concentrate on the aspect of finding pivot selection heuristics for the phase one problem with the objective to improve the performance of the algorithm. If no artificial variables are basic, it means that an optimum solution for phase one is found. In our approach we show how a feasible solution can be obtained by using an evaluation function. This evaluation function guides the pivot process of the simplex method in such a way that it will, as a first priority, try to pivot artificial variables out of the basis. We show how this evaluation function can be used in conjunction with other well-known column selection heuristics. We also show how this approach can be used with multiple pricing, a technique that strives to minimize data transformations at each step. The evaluation function is also employed to improve numerical stability in the solution process. Experimental work on some problems from the NETLIB test suite is presented. This empirical work also compares this approach to well-known column selection heuristics.