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

✍ Scribed by S. W. Sloan

• Publisher: John Wiley and Sons
• Year: 1988
• Tongue: English
• Weight: 863 KB
• Volume: 26
• Category: Article
• ISSN: 0029-5981
• DOI: 10.1002/nme.1620261207

✦ Synopsis

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 twophase 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. Recently, Best and Ritter' have published an alternative procedure, known as the active set algorithm, which has the following canonical form:

Minimize cTx

Subject to

A,x < b,

where c is a vector of objective function coefficients of length n, A, is an m x n matrix of inequality constraint coefficients, A, is an r x n matrix of equality constraint coefficients, b, is a vector of length m, b, is a vector of length r and x is an unknown vector of length n which is to be determined. The active set algorithm has a very simple geometric interpretation, works with an active constraint matrix of dimension n x n and is ideally suited to problems where n < m + r .

This paper describes an efficient implementation of the active set procedure which employs a steepest edge heuristic for choosing the search direction at each iteration. The steepest edge scheme is similar to that developed by Goldfarb and ReidZ for the revised simplex method and is relatively simple to implement. We also describe a complete two-phase algorithm for the active set method which incorporates a crash procedure and uses one artificial variable to determine if the linear programming problem has a feasible solution in phase one. The effectiveness of the proposed algorithm is illustrated by applying it to a variety of sparse linear programming problems that arise in the application of classical plasticity theory.