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-functionwhere 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 suitablymodified 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 wellstructured 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 themore 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.