A primal-dual simplex method for linear programs

A primal-dual simplex method for linear programs

0.00 Avg rating0 Votes
Article ID: iaor1995330
Country: Netherlands
Volume: 13
Issue: 4
Start Page Number: 233
End Page Number: 237
Publication Date: May 1993
Journal: Operations Research Letters
Authors:
Abstract:

A primal-dual algorithm is developed that optimizes a dual program in concert with improving primal infeasibility. The key distinction from the classic primal-dual simplex method is that the present algorithm uses a much smaller working basis to determine a dual ascent direction quickly. By maintaining partial primal feasilibity while improving the dual objective, the number of infeasible constraints is monotonically reduced to zero. Finite convergence to an optimal primal-dual pair can then be shown in the same manner as the simplex method. Computational experience on large generalized network linear programs demonstrates the algorithm’s promise.

Reviews

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