Optimization Online


Generalized Bundle Methods for Sum-Functions with ``Easy'' Components: Applications to Multicommodity Network Design

Antonio Frangioni(frangio***at***di.unipi.it)
Enrico Gorgone(egorgone***at***deis.unical.it)

Abstract: We propose a modification to the (generalized) bundle scheme for minimization of a convex nondifferentiable sum-function in the case where some of the components are ``easy'', that is, they are Lagrangian functions of explicitly known convex programs with ``few'' variables and constraints. This happens in many practical cases, particularly within applications to combinatorial optimization. In this case one can insert in the master problem a suitably modified representation of the original convex subproblem, as an alternative to iteratively inner-approximating it by means of the produced extreme points, thus providing the algorithm with exact information about a part of the objective function, possibly leading to performance improvements. This is shown to happen in at least one relevant application: the computation of tight lower bounds for Fixed-Charge Multicommodity Min-Cost Flow problems.

Keywords: Nondifferentiable Optimization, Bundle methods, Lagrangian Relaxation, Partial Dantzig-Wolfe Decomposition, Multicommodity Network Design

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Network Optimization

Citation: Technical Report 11-08, Dipartimento di Informatica, Universit\`a di Pisa

Download: [PDF]

Entry Submitted: 06/03/2011
Entry Accepted: 06/03/2011
Entry Last Modified: 06/03/2011

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 Optimization Society