Finding an initial feasible solution in linear programming

In most approaches, the resolution of a linear programming problem needs a starting feasible solution. Among the techniques commonly used to overcome this difficulty, the construction of an artificial linear program having a known feasible solution and then the application of the big M method is certainly the most popular. In this paper the authors study some criteria that provide an estimation of M, in order to get an optimal solution of the original linear program from the feasible solution of the constructed artificial linear program. They also provide some techniques for updating M, which allow to avoid the undesirable consequences that arise from an initial unsafe estimate of M. Although the fact that the main discussed results are oriented to the simplex method at the end of the paper the authors extend some of the results to interior point methods.