Initialization of the simplex algorithm: An artificial-free approach

The simplex algorithm requires artificial variables for solving linear programs which lack primal feasibility at the origin point. We present a new general purpose solution algorithm which obviates the use of artificial variables. The algorithm searches for a feasible segment of a boundary hyperplane (a face of feasible region or an intersection of several faces) by using rules similar to the ordinary simplex.