A parametric algorithm for convex cost network flow and related problems

DOI10.1016/0377-2217(84)90076-6zbMath0532.90034OpenAlexW2052415705MaRDI QIDQ789313

J. L. Batra, S. K. Gupta, Ravindra K. Ahuja

Publication date: 1984

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(84)90076-6

zbMATH Keywords

computational complexityshortest pathsminimum cost flowcomputational resultspolynomial boundednesscontext cost network flow problemCPM networklarge size problemsoptimum basis structureoptimum capacity expansionparametric algorithmproject cost curve

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)

Related Items (5)

Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs ⋮ An integer fuzzy transportation problem ⋮ On a new class of bilevel programming problems and its use for reformulating mixed integer problems ⋮ Complexity and algorithms for nonlinear optimization problems ⋮ Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for optimizing network flow capacity under economies of scale
• Optimum flows in general communication networks
• A Network Flow Computation for Project Cost Curves
• Linear Programming under Uncertainty
• The Allocation of Aircraft to Routes—An Example of Linear Programming Under Uncertain Demand
• Increasing the Capacity of a Network: The Parametric Budget Problem
• Monotone networks
• Critical-Path Planning and Scheduling: Mathematical Basis
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Calculating Maximal Flows in a Network with Positive Gains
• A Primal Algorithm to Solve Network Flow Problems with Convex Costs
• On Max Flows with Gains and Pure Min-Cost Flows
• Solving the Project Time/Cost Tradeoff Problem Using the Minimal Cut Concept
• A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
• The minimal cost flow problem with convex costs
• A Direct Search Method to Locate Negative Cycles in a Graph

This page was built for publication: A parametric algorithm for convex cost network flow and related problems