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: | Curet Norman D. |
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.