Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems

DOI10.1007/BF02072644MaRDI QIDQ1308671zbMATH OpenFDO

Authors Renato De Leone, Manlio Gaudioso, Maria Flavia Monaco

Publication date 10 December 1993

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02072644

zbMATH Keywords

bundle algorithmmulticommodity network flownonsmooth optimizationparallel implementationresource directive decomposition

Mathematics Subject Classification ID

Nonsmooth analysis (49J52) Parallel numerical computation (65Y05) Deterministic network models in operations research (90B10) Applications of mathematical programming (90C90)

Review text

Multicommodity network flow problems are tackled by using a resource directive decomposition technique. First, decision variables representing a feasible sharing of the resource among all different commodities are introduced. Then the problem is decomposed in mincost single commodity network flow problems. Finally, a master problem is solved for finding an improved sharing of the resources. Since the objective function of the master problem is non-differentiable, a bundle algorithm is used for solving it. The adopted decomposition scheme is particularly suitable for parallel implementation. The results are also extended to the nonlinear, separable case.

Recommendations

• Parallel Decomposition of Multicommodity Network Flows Using a Linear-Quadratic Penalty Algorithm
• A Parallel Projection for the Multicommodity Network Model
• A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems
• Solving nonlinear multicommodity flow problems by the analytic center cutting plane method
• Simplex and Interior Point Specialized Algorithms for Solving Nonoriented Multicommodity Flow Problems

Cites work

• A bundle type approach to the unconstrained minimization of convex nonsmooth functions
• A Parallel Network Equilibration Algorithm for a Class of Constrained Matrix Problems
• A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
• An Interior Point Method for Block Angular Optimization
• An iterative row-action method for interval convex programming
• scientific article; zbMATH DE number 4147424 (Why is no real title available?)
• scientific article; zbMATH DE number 3791941 (Why is no real title available?)
• scientific article; zbMATH DE number 3791942 (Why is no real title available?)
• scientific article; zbMATH DE number 51132 (Why is no real title available?)
• scientific article; zbMATH DE number 3296905 (Why is no real title available?)
• Introduction to sensitivity and stability analysis in nonlinear programming
• Massively parallel implementation of the splitting equilibration algorithm
• Massively Parallel Row-Action Algorithms for Some Nonlinear Transportation Problems
• Primal Resource-Directive Approaches for Optimizing Nonlinear Decomposable Systems
• Proximity control in bundle methods for convex nondifferentiable minimization

Cited in

(3)

• Bundle methods for sum-functions with ``easy components: applications to multicommodity network design
• A NONSMOOTH OPTIMIZATION APPROACH TO NONLINEAR MULTICOMMODITY NETWORK FLOW PROBLEMS
• Cyclically monotone non-optimal N-marginal transport plans and Smirnov-type decompositions for N-flows

This page was built for publication: Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1308671)