Article ID: | iaor20032524 |
Country: | Germany |
Volume: | 94 |
Issue: | 1 |
Start Page Number: | 41 |
End Page Number: | 69 |
Publication Date: | Jan 2002 |
Journal: | Mathematical Programming |
Authors: | Maculan Nelson, Bahiense L., Sagastizbal C. |
Keywords: | bundle methods |
We revise the Volume Algorithm (VA) for linear programming and relate it to bundle methods. When first introduced, VA was presented as a subgradient-like method for solving the original problem in its dual form. In a way similar to the serious/null steps philosophy of bundle methods, VA produces green, yellow or red steps. In order to give convergence results, we introduce in NA a precise measure for the improvement needed to declare a green or serious step. This addition yields a revised formulation (RVA) that is halfway between VA and a specific bundle method, that we call BVA. We analyze the convergence properties of both RVA and BVA. Finally, we compare the performance of the modified algorithms versus VA on a set of Rectilinear Steiner problems of various sizes and increasing complexity, derived from real world very large scale integration design instances.