Feasibility Achievement without the Hassle of Artificial Variables: A Computational Study

Abstract

The purpose of this article is to encourage students and teachers to use a simple technique for finding feasible solution of an LP. This technique is very simple but unfortunately not much practiced in the textbook literature yet. This article discusses an overview, advantages, computational experience of the method. This method provides some pronounced benefits over Dantzig’s simplex method phase 1. For instance, it does not require any kind of artificial variables or artificial constraints; it could directly start with any infeasible basis of an LP. Throughout the procedure it works in original variables space hence revealing the true underlying geometry of the problem. Last but not the least; it is a handy tool for students to quickly solve a linear programming problem without indulging with artificial variables. It is also beneficial for the teachers who want to teach feasibility achievement as a separate topic before teaching optimality achievement. Our primary result shows that this method is much better than simplex phase 1 for practical Net-lib problems as well as for general random LPs.