Relaxation Methods for Network Flow Problems with Convex Arc Costs

DOI10.1137/0325067zbMath0641.90036OpenAlexW2035934281MaRDI QIDQ3783055

Dimitri P. Bertsekas, Patrick A. Hosein, Paul Tseng

Publication date: 1987

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0325067

zbMATH Keywords

parallel computationlinear minimum cost network flowdual Gauss-Seidel type relaxation methodlinear and strictly convex possibly nondifferentiable arc costssingle commodity network flow

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Related Items (31)

Data parallel computing for network-structured optimization problems ⋮ Application of the dual active set algorithm to quadratic network optimization ⋮ Proximal minimizations with \(D\)-functions and the massively parallel solution of linear network programs ⋮ PARALLELIZATION STRATEGIES OF A ROW-ACTION METHOD FOR MULTICOMMODITY NETWORK FLOW PROBLEMS ⋮ Dual coordinate step methods for linear network flow problems ⋮ Asynchronous gradient algorithms for a class of convex separable network flow problems ⋮ Network games; adaptations to Nash-Cournot equilibrium ⋮ Solving multistage stochastic network programs on massively prallel computers ⋮ Computational comparisons of dual conjugate gradient algorithms for strictly convex networks. ⋮ Relaxation methods for problems with strictly convex separable costs and linear constraints ⋮ A modified self-adaptive dual ascent method with relaxed stepsize condition for linearly constrained quadratic convex optimization ⋮ Relaxation methods for monotropic programs ⋮ Matrix scaling, entropy minimization, and conjugate duality. II: The dual problem ⋮ A survey of dynamic network flows ⋮ Unnamed Item ⋮ Models for multimode multicommodity location problems with interdepot balancing requirements ⋮ Decomposition algorithm for convex differentiable minimization ⋮ A survey on the continuous nonlinear resource allocation problem ⋮ An ε-Relaxation method for generalized separable convex cost network flow problems ⋮ On the linear convergence of the alternating direction method of multipliers ⋮ A partial linearization method for the traffic assignment problem ⋮ Convergent Lagrangian heuristics for nonlinear minimum cost network flows ⋮ On the dual coordinate ascent approach for nonlinear networks ⋮ A proximal subgradient projection algorithm for linearly constrained strictly convex problems ⋮ Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité ⋮ About saddle values of a class of convex-concave functions ⋮ The auction algorithm: A distributed relaxation method for the assignment problem ⋮ Descent methods for convex essentially smooth minimization ⋮ On the convergence of the coordinate descent method for convex differentiable minimization ⋮ Asymptotic properties of the Fenchel dual functional and applications to decomposition problems ⋮ A unified description of iterative algorithms for traffic equilibria

Uses Software

• NETGEN

This page was built for publication: Relaxation Methods for Network Flow Problems with Convex Arc Costs