The Volume Algorithm revisited: relation with bundle methods

Laura Bahiense (laurapsr-inc.com)
Nelson Maculan (nelson.maculanlipn.univ-paris13.fr)
Claudia Sagastizábal (sagastizimpa.br)

Abstract: 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 VA 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 VLSI design instances.

Keywords: volume algorithm, bundle methods, Steiner problems

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Preprint Serie A #2001/106 October/2001 IMPA Estrada Dona Castorina 110, Jardim Botanico, Rio de Janeiro, RJ, CEP 22460-320, Brazil

Download: [Postscript]

Entry Submitted: 11/01/2001
Entry Accepted: 11/06/2001
Entry Last Modified: 11/06/2001

Modify/Update this entry