Optimization Online


The Volume Algorithm revisited: relation with bundle methods

Laura Bahiense (laura***at***psr-inc.com)
Nelson Maculan (nelson.maculan***at***lipn.univ-paris13.fr)
Claudia Sagastizábal (sagastiz***at***impa.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society