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

We propose a version of the bundle scheme for convex nondifferentiable optimization suitable for the case of a sum-function where some of the components are "easy", that is, they are Lagrangian functions of explicitly known compact convex programs. This corresponds to a stabilized partial Dantzig-Wolfe decomposition, where suitably modified representations of the "easy" convex subproblems are inserted in the master problem as an alternative to iteratively inner-approximating them by extreme points, thus providing the algorithm with exact information about a part of the dual objective function. The resulting master problems are potentially larger and less well-structured than the standard ones, ruling out the available specialized techniques and requiring the use of general-purpose solvers for their solution; this strongly favors piecewise-linear stabilizing terms, as opposed to the more usual quadratic ones, which in turn may have an adverse effect on the convergence speed of the algorithm, so that the overall performance may depend on appropriate tuning of all these aspects. Yet, very good computational results are obtained in at least one relevant application: the computation of tight lower bounds for Fixed-Charge Multicommodity Min-Cost Flow problems.