A strictly improving linear programming Phase I algorithm

A strictly improving linear programming Phase I algorithm

0.00 Avg rating0 Votes
Article ID: iaor19941139
Country: Switzerland
Volume: 46/47
Issue: 1/4
Start Page Number: 409
End Page Number: 430
Publication Date: Dec 1993
Journal: Annals of Operations Research
Authors: , ,
Keywords: programming: nonlinear
Abstract:

Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do), the authors have developed a new Phase I algorithm that is impervious to degeneracy. The new algorithm solves a non-negative least-squares problem in order to find a Phase I solution. In each iteration, a simple two-variable least-squares subproblem is used to select an incoming column to augment a set of independent columns (called ‘basic’) to get a strictly better fit to the right-hand side. Although this is analogous in many ways to the simplex method, it can be proved that strict improvement is attained at each iteration, even in the presence of degeneracy. Thus cycling cannot occur, and convergence is guaranteed. This algorithm is closely related to a number of existing algorithms proposed for non-negative least-squares and quadratic programs. When used on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3.5 times faster than a particular implementation of the simplex method; on some problems, it was over 10 times faster. Best results were generally seen on the more degenerate problems.

Reviews

Required fields are marked *. Your email address will not be published.