A steepest edge active set algorithm for solving sparse linear programming problems

A steepest edge active set algorithm is described which is suitable for solving linear programming problems where the constraint matrix is sparse and has more rows than columns. The algorithm uses a steepest edge criterion for selecting the search direction at each iteration and recurrence relations are derived which enable it to execute efficiently. The canonical form for the active set method is convenient for many applications and may be exploited to devise a simple crash procedure which is employed prior to phase one. A complete two-phase algorithm which incorporates the crash procedure is outlined. Only one artificial variable is needed to determine if the linear programming problem has a feasible solution in phase one. Some computational results are given to illustrate the effectiveness of the algorithm for a range of sparse linear programming problems. Comparisons between the steepest edge criterion and the traditional Dantzig criterion suggest that the former usually requires fewer iterations and often leads to substantial savings for large problems.