In this work, we will first extend the full artificial basis technique presented in , to solve problems in general form, then we will combine a crash procedure with a single artificial variable technique in order to find an initial support feasible solution for the initialization of the support method.
This technique is efficient for solving practical problems.
In [25–31], crash procedures are developed to find a good initial basis.
In , a two-phase support method with one artificial variable for solving linear programming problems was developed.
The results of the numerical comparison revealed that finding the initial support by the Gauss elimination method consumes much time, and transforming the equality constraints to inequality ones increases the dimension of the problem.
Hence, the proposed approaches are competitive with the full artificial basis simplex method for solving small problems, but they are not efficient to solve large problems.After finding the initial support, we search a feasible solution by adding only one artificial variable to the original problem, thus we get an auxiliary problem with an evident support feasible solution.An experimental study has been carried out on some NETLIB test problems.The first technique used to find an initial basic feasible solution for the simplex method is the full artificial basis technique .In [21, 22], the authors developed a technique using only one artificial variable to initialize the simplex method.After that, in the second phase, we solve the original problem with the primal support method .In [33, 34], we have suggested two approaches to initialize the primal support method with nonnegative variables and bounded variables: the first approach consists of applying the Gauss elimination method with partial pivoting to the system of linear equations corresponding to the main constraints and the second consists of transforming the equality constraints to inequality constraints.In 1984, Karmarkar presented for the first time an interior point algorithm competitive with the simplex method on large-scale problems .The efficiency of the simplex method and its generalizations depends enormously on the first initial point used for their initialization.In order to study the performances of the suggested algorithm, an implementation under the MATLAB programming language has been developed.Finally, we carry out an experimental study about CPU time and iterations number on a large set of the NETLIB test problems.