A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems

Morton Klein
Morton Klein
Columbia University
Search for more papers by this author

Columbia University

Published Online:1 Nov 1967https://doi.org/10.1287/mnsc.14.3.205

Abstract

A simple procedure is given for solving minimal cost flow problems in which feasible flows are maintained throughout. It specializes to give primal algorithms for the assignment and transportation problems. Convex cost problems can also be handled.

Cited by
- An advanced Successive Derivative Shortest Path algorithm for concave cost network flow problems
  Operations Research Perspectives, Vol. 14
- Decomposition Algorithm for a Nonlinear Three-Index Transportation Problem
  12 March 2025 | Mathematics, Vol. 13, No. 6
- Air Corridor Planning for Urban Drone Delivery: Complexity Analysis and Comparison via Multi-Commodity Network Flow and Graph Search
  Transportation Research Part E: Logistics and Transportation Review, Vol. 193
- Accurate prediction of RNA secondary structure including pseudoknots through solving minimum-cost flow with learned potentials
  9 March 2024 | Communications Biology, Vol. 7, No. 1
- Using Probe Counts to Provide High-Resolution Detector Data for a Microscopic Traffic Simulation
  28 April 2024 | Vehicles, Vol. 6, No. 2
- An Innovative Control Approach for Cyber-Physical Transportation Systems: The Case of Monte-Carlo Workflow Computations
- Automatic vehicle trajectory data reconstruction at scale
  Transportation Research Part C: Emerging Technologies, Vol. 160
- Properties of B2B Invoice Graphs and Detection of Structures
  21 February 2024
- Modeling and solving a corporate vehicle-sharing problem combined with other modes of transport
  EURO Journal on Transportation and Logistics, Vol. 13
- Online Min Cost Circulation for Multi-Object Tracking on Fragments
- A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
  20 June 2023 | Networks, Vol. 82, No. 2
- A framework to estimate a long-term power shortage risk following large-scale earthquake and tsunami disasters
  27 March 2023 | PLOS ONE, Vol. 18, No. 3
- Route Network Planning for Urban Drone Delivery: Network Flow Theory or Graph Search Algorithms?
  1 January 2023 | SSRN Electronic Journal, Vol. 117
- Efficient Flow-Based Scheduling for Geo-Distributed Simulation Tasks in Collaborative Edge and Cloud Environments
  IEEE Transactions on Parallel and Distributed Systems, Vol. 33, No. 12
- An Improved End-to-End Multi-Target Tracking Method Based on Transformer Self-Attention
  15 December 2022 | Remote Sensing, Vol. 14, No. 24
- Optimization of earthworks planning: a systematic mapping study
  Canadian Journal of Civil Engineering, Vol. 49, No. 12
- Approximate Wasserstein attraction flows for dynamic mass transport over networks
  Automatica, Vol. 143
- Minimum cost Eulerian cycles in road networks
- Food flows between counties in the United States from 2007 to 2017
  28 February 2022 | Environmental Research Letters, Vol. 17, No. 3
- Efficient Dynamic Deployment of Simulation Tasks in Collaborative Cloud and Edge Environments
  4 February 2022 | Applied Sciences, Vol. 12, No. 3
- Primal-Dual Methods and Minimum Cost Flow
  6 July 2022
- Margin of victory for tournament solutions
  Artificial Intelligence, Vol. 302
- DRMaestro: orchestrating disaggregated resources on virtualized data-centers
  6 March 2021 | Journal of Cloud Computing, Vol. 10, No. 1
- Algorithms for the metric ring star problem with fixed edge-cost ratio
  17 May 2019 | Journal of Combinatorial Optimization, Vol. 42, No. 3
- A Comprehensive Literature Review on Transportation Problems
  24 September 2021 | International Journal of Applied and Computational Mathematics, Vol. 7, No. 5
- Fundamentals of Transportation Problem
  30 June 2021 | International Journal of Engineering and Advanced Technology, Vol. 10, No. 5
- Efficient Algorithms for Identifying Loop Formation and Computing θ Value for Solving Minimum Cost Flow Network Problems
  28 June 2021 | WSEAS TRANSACTIONS ON CIRCUITS AND SYSTEMS, Vol. 20
- Discrete Convex Analysis and Its Applications in Operations: A Survey
  1 June 2021 | Production and Operations Management, Vol. 30, No. 6
- A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks
  European Journal of Operational Research, Vol. 290, No. 3
- Effects of Air Emission Externalities on Optimal Ridesourcing Fleet Electrification and Operations
  19 February 2021 | Environmental Science & Technology, Vol. 55, No. 5
- ReMOT: A model-agnostic refinement for multiple object tracking
  Image and Vision Computing, Vol. 106
- SCIM: universal single-cell matching with unpaired feature sets
  29 December 2020 | Bioinformatics, Vol. 36, No. Supplement_2
- The minimum cost flow finding under fuzzy intuitionistic conditions
  Journal of Physics: Conference Series, Vol. 1703, No. 1
- A Shift-Daily Planning of Freight Trains Composition and Transit Using Maximum Network Flow Approach
- References
  17 April 2020
- An Efficient Algorithm for Solving Minimum Cost Flow Problem with Complementarity Slack Conditions
  Mathematical Problems in Engineering, Vol. 2020
- Graphentheorie
  10 December 2019
- Concurrent container scheduling on heterogeneous clusters with multi-resource constraints
  Future Generation Computer Systems, Vol. 102
- Balanced-flow algorithm for path network planning in hierarchical spaces
  Theoretical Computer Science, Vol. 803
- Integrated reconfiguration of both supply and demand for evacuation planning
  Transportation Research Part E: Logistics and Transportation Review, Vol. 130
- Network Flow Algorithms
  21 August 2019 | , Vol. 194
- Mapping ground displacement by a multiple phase difference-based InSAR approach: with stochastic model estimation and turbulent troposphere mitigation
  9 March 2019 | Journal of Geodesy, Vol. 93, No. 9
- Food flows between counties in the United States
  26 July 2019 | Environmental Research Letters, Vol. 14, No. 8
- Optimal K-node disruption on a node-capacitated network
  3 May 2018 | Optimization Letters, Vol. 13, No. 4
- A New Cellular-Based Redundant TSV Structure for Clustered Faults
  IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 27, No. 2
- Convexification of generalized network flow problem
  8 January 2018 | Mathematical Programming, Vol. 173, No. 1-2
- Dynamical optimal transport on discrete surfaces
  4 December 2018 | ACM Transactions on Graphics, Vol. 37, No. 6
- Towards negative cycle canceling in wind farm cable layout optimization
  10 October 2018 | Energy Informatics, Vol. 1, No. S1
- Reservoir Management Using a Network Flow Optimization Model Considering Quadratic Convex Cost Functions on Arcs
  12 May 2018 | Water Resources Management, Vol. 32, No. 10
- QuadriFlow: A Scalable and Robust Method for Quadrangulation
  8 August 2018 | Computer Graphics Forum, Vol. 37, No. 5
- Collaborative vehicle routing: A survey
  European Journal of Operational Research, Vol. 268, No. 1
- Cost-efficient scheduling of FAST observations
  16 February 2018 | Experimental Astronomy, Vol. 45, No. 1
- Privacy-Preserving Trade Chain Detection
  7 September 2018
- Min-Max-Flow Based Algorithm for Evacuation Network Planning in Restricted Spaces
  16 November 2018
- Minimum Cost Flows
  14 March 2018
- Flüsse mit minimalen Kosten
  25 July 2018
- Quadratically Regularized Optimal Transport on Graphs
  SIAM Journal on Scientific Computing, Vol. 40, No. 4
- Machine Learning-Assisted Network Inference Approach to Identify a New Class of Genes that Coordinate the Functionality of Cancer Networks
  1 August 2017 | Scientific Reports, Vol. 7, No. 1
- Minimum cost flow problem formulation for the static vehicle allocation problem with stochastic lane demand in truckload strategic planning
  17 July 2017 | Transportmetrica A: Transport Science, Vol. 13, No. 10
- Taxonomy Induction Using Hypernym Subsequences
  6 November 2017
- MULTICOMMODITY NETWORK FLOWS WITH NONCONVEX ARC COSTS
  1 September 2017 | Pesquisa Operacional, Vol. 37, No. 3
- A strongly polynomial Contraction-Expansion algorithm for network flow problems
  Computers & Operations Research, Vol. 84
- Trajectory Ensemble: Multiple Persons Consensus Tracking Across Non-overlapping Multiple Cameras over Randomly Dropped Camera Networks
- Optimal Operation and Economic Value of Energy Storage at Consumer Locations
  IEEE Transactions on Automatic Control, Vol. 62, No. 2
- Flow Tasks in Networks in Crisp Conditions
  31 July 2016
- Discovering Injective Mapping Between Relations in Astrophysics Databases
  4 October 2017
- Dependable Dynamic Routing for Urban Transport Systems Through Integer Linear Programming
  19 October 2017
- Impacts of an Ice-Free Northeast Passage on LNG Trading: Transport Routes and Optimal Capacity Planning
  SSRN Electronic Journal, Vol. 7
- The impact of Polish unconventional production on the regional distribution of natural gas supply and transit: A scenario analysis
  Energy Strategy Reviews, Vol. 10
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
  14 January 2016
- $\text{E}^{3}$ MC: Improving Energy Efficiency via Elastic Multi-Controller SDN in Data Center Networks
  IEEE Access, Vol. 4
- About the minimum mean cycle-canceling algorithm
  Discrete Applied Mathematics, Vol. 196
- Multimodal multi-flow problem with transformation : Application to waste supply chain
- Automatic target recognition using discrimination based on optimal transport
- Minimum-cost flow algorithms: an experimental evaluation
  1 April 2014 | Optimization Methods and Software, Vol. 30, No. 1
- Securely Solving Classical Network Flow Problems
  17 March 2015
- Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm
  24 June 2015
- Smoothed Analysis of the Successive Shortest Path Algorithm
  SIAM Journal on Computing, Vol. 44, No. 6
- Uncertain minimum cost flow problem
  5 December 2013 | Soft Computing, Vol. 18, No. 11
- Optimal Water System Operation Using Graph Theory Algorithms
  Procedia Engineering, Vol. 89
- The problem of maximum flow with minimum attainable cost in a network
  4 October 2012 | OPSEARCH, Vol. 50, No. 2
- Circulations
- Splittable Single Source-Sink Routing on CMP Grids: A Sublinear Number of Paths Suffice
- Capacity-Constrained Network-Voronoi Diagram: A Summary of Results
- References
- Adaptive scheduling strategies for cloud‐based resource infrastructures
  30 January 2012 | Security and Communication Networks, Vol. 5, No. 10
- Association control algorithms for handoff frequency minimization in mobile wireless networks
  28 February 2012 | Wireless Networks, Vol. 18, No. 5
- Flow constrained minimum cost flow problem
  24 March 2012 | OPSEARCH, Vol. 49, No. 2
- Minimum Cost Flows
  27 October 2011
- Flüsse mit minimalen Kosten
  4 May 2012
- Phase Unwrapping for Very Large Interferometric Data Sets
  IEEE Transactions on Geoscience and Remote Sensing, Vol. 49, No. 10
- Minimal-cost network flow problems with variable lower bounds on arc flows
  Computers & Operations Research, Vol. 38, No. 8
- A network approach to modeling the multi-echelon spare-part inventory system with backorders and interval-valued demand
  International Journal of Production Economics, Vol. 132, No. 1
- Minimum Cost Flows
  15 February 2011
- Adaptive Optimal Global Resource Scheduling for a Cloud-Based Virtualized Resource Pool
- Flussi di costo minimo
- An efficient heuristic for medium-term planning in shampoo production
  International Journal of Production Economics, Vol. 129, No. 1
- Fast Algorithms for Specially Structured Minimum Cost Flow Problems with Applications
  Balachandran Vaidyanathan,
  Ravindra K. Ahuja,
  13 September 2010 | Operations Research, Vol. 58, No. 6
- From Microgrids to Smart Grids: Modeling and simulating using graphs. Part I active power flow
- Algorithms for storage allocation based on client preferences
  27 August 2009 | Journal of Combinatorial Optimization, Vol. 19, No. 3
- Flots de coût minimum
- Solving coalitional resource games
  Artificial Intelligence, Vol. 174, No. 1
- Bibliography
  15 August 2011
- The Minimum-Cost and Maximum-Flow Algorithm for Railway Empty Cars Distribution
  26 April 2012
- Implementation of a new Preference Based Final Year Project title selection system for undergraduate engineering students in UNITEN
- A faster polynomial algorithm for the unbalanced Hitchcock transportation problem
  Operations Research Letters, Vol. 36, No. 4
- Cycle‐based algorithms for multicommodity network flow problems with separable piecewise convex costs
  14 December 2007 | Networks, Vol. 51, No. 2
- Minimum Cost Flows
- Flüsse mit minimalen Kosten
- A Zero-Space algorithm for Negative Cost Cycle Detection in networks
  Journal of Discrete Algorithms, Vol. 5, No. 3
- Minimum Cost Flows
- Algorithms and Complexity
- Shortest Path Algorithms
- APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS
  20 November 2011 | International Journal of Foundations of Computer Science, Vol. 16, No. 02
- Visualizing, Finding and Packing Dijoins
- Efficient Algorithms for the Electric Power Transaction Problem
- A SURVEY OF COMBINATORIAL MAXIMUM FLOW ALGORITHMS ON A NETWORK WITH GAINS(Network Design, Control and Optimization)
  Journal of the Operations Research Society of Japan, Vol. 47, No. 4
- Minimum convex cost flow problem
- A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
  Kevin D. Wayne,
  1 August 2002 | Mathematics of Operations Research, Vol. 27, No. 3
- File Transfer Tree Problems
  8 November 2002
- Minimum Cost Flows
- Configuration of reserved delivery subnetworks
- Sokoban: Enhancing general single-agent search methods using domain knowledge
  Artificial Intelligence, Vol. 129, No. 1-2
- Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks
  Operations Research Letters, Vol. 27, No. 5
- New polynomial-time cycle-canceling algorithms for minimum-cost flows
  1 January 2000 | Networks, Vol. 36, No. 1
- Relaxed Most Negative Cycle and Most Positive Cut Canceling Algorithms for Minimum Cost Flow
  Maiko Shigeno,
  Satoru Iwata,
  S. Thomas McCormick,
  1 February 2000 | Mathematics of Operations Research, Vol. 25, No. 1
- A polynomial combinatorial algorithm for generalized minimum cost flow
  1 May 1999
- A cycle augmentation algorithm for minimum cost multicommodity flows on a ring
- Penelope's graph: a hard minimum cost tension instance
  Theoretical Computer Science, Vol. 194, No. 1-2
- Sokoban: Evaluating standard single-agent search techniques in the presence of deadlock
  29 July 2005
- Valuated Matroid Intersection II: Algorithms
  SIAM Journal on Discrete Mathematics, Vol. 9, No. 4
- Negative-cycle detection algorithms
  6 June 2005
- Suboptimal scheduling of injection molding process using fuzzy optimization technique
- Three-dimensional densitometric reconstruction and visualization of stenosed coronary artery segments
  Computerized Medical Imaging and Graphics, Vol. 19, No. 2
- Computing maximum mean cuts
  Discrete Applied Mathematics, Vol. 52, No. 1
- Tight bounds on the number of minimum-mean cycle cancellations and related results
  Algorithmica, Vol. 11, No. 3
- Two strongly polynomial cut cancelling algorithms for minimum cost network flow
  Discrete Applied Mathematics, Vol. 46, No. 2
- Analysis of the Degree of Parallelism for Non-Polynomial, Polynomial, Strongly Polynomial Algorithms for Solving the Minimum Cost Flow Problem
- An application of the lagrangean relaxation method to unit commitment scheduling in a power generation system with pumped-storage units
  Computers & Industrial Engineering, Vol. 24, No. 1
- Polynomial-time primal simplex algorithms for the minimum cost network flow problem
  Algorithmica, Vol. 8, No. 1-6
- Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
  Operations Research Letters, Vol. 12, No. 4
- Negative circuits for flows and submodular flows
  Discrete Applied Mathematics, Vol. 36, No. 2
- Some Recent Advances in Network Flows
  SIAM Review, Vol. 33, No. 2
- The stochastic multicommodity flow problem
  11 October 2006 | Networks, Vol. 20, No. 2
- Finding minimum-cost circulations by canceling negative cycles
  1 October 1989 | Journal of the ACM, Vol. 36, No. 4
- Note on Weintraub’s Minimum-Cost Circulation Algorithm
  SIAM Journal on Computing, Vol. 18, No. 3
- Chapter IV Network flows
- Temporally repeated flow algorithms for dynamic min cost flows
- The Improvements to a Network Flow Approach to Reconstruction of the Vascular Cross Sections from Two Orthogonal Projections
  Biomedizinische Technik/Biomedical Engineering, Vol. 34, No. s1
- A transportation type aggregate production model with bounds on inventory and backordering
  European Journal of Operational Research, Vol. 35, No. 3
- Combinatorial algorithms for the generalized circulation problem
- Pickup and Delivery of Partial Loads with “Soft” Time Windows
  American Journal of Mathematical and Management Sciences, Vol. 6, No. 3-4
- 3-D reconstruction of coronary arterial segments from two projections
- On a nonbasic dual method for the transportation problem
  26 February 2009
- An efficient implementation of the network simplex method
  26 February 2009
- OPTIMAL ENERGY EXCHANGE IN A DECENTRALIZED POWER POOL
- Optimal Energy Exchange in a Decentralized Power Pool
  IFAC Proceedings Volumes, Vol. 18, No. 9
- A hybrid algorithm for solving convex separable network flow problems
  Zeitschrift für Operations Research, Vol. 29, No. 3
- 3-D reconstruction of homogeneous objects from two poisson-distributed projections
  Pattern Recognition Letters, Vol. 3, No. 2
- A parametric algorithm for convex cost network flow and related problems
  European Journal of Operational Research, Vol. 16, No. 2
- Optimal control of water distribution systems by network flow theory
  IEEE Transactions on Automatic Control, Vol. 29, No. 4
- Optimization on Graphs and Networks
- The linear transportation problem
- Ein partitionierungsalgorithmus zur distanzberechnung auf Verkehrsnetzen
  1 December 2008 | Mathematische Operationsforschung und Statistik. Series Optimization, Vol. 15, No. 3
- The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
  Mathematical Programming, Vol. 25, No. 2
- Recent Developments in Computer Implementation Technology for Network Flow Algorithms
  25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 20, No. 4
- Weighted min cost flows
  European Journal of Operational Research, Vol. 11, No. 2
- On three basic methods for solving bottleneck transportation problems
  Naval Research Logistics Quarterly, Vol. 29, No. 3
- A network flow approach to reconstruction of the left ventricle from two projections
  Computer Graphics and Image Processing, Vol. 18, No. 1
- Bibliography
- Comparison of different methods for the calculation of traffic matrices
  Annales des Télécommunications, Vol. 35, No. 3-4
- A Network Flow Model for Forecasting and Evaluating Criminal Displacement
  1 May 1979 | Evaluation Quarterly, Vol. 3, No. 2
- Testing of a large-scale network optimization program
  Mathematical Programming, Vol. 15, No. 1
- A note on primal network flow algorithms
  Zeitschrift für Operations Research, Vol. 22, No. 1
- Das lineare Transportproblem
- On Max Flows with Gains and Pure Min-Cost Flows
  SIAM Journal on Applied Mathematics, Vol. 32, No. 2
- Past, present and future of large scale transshipment computer codes and applications
  Computers & Operations Research, Vol. 2, No. 2
- Survey of Deterministic Networks
  9 July 2007 | A I I E Transactions, Vol. 7, No. 3
- Survey of Deterministic Networks
  16 July 2007 | A I I E Transactions, Vol. 8, No. 1
- A Node Elimination Method For Finding Negative Cycles In A Directed Graph
  25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 13, No. 2
- An improved version of the out-of-kilter method and a comparative study of computer codes
  Mathematical Programming, Vol. 7, No. 1
- More pathological examples for network flow problems
  Mathematical Programming, Vol. 5, No. 1
- A bad network problem for the simplex method and other minimum cost flow algorithms
  Mathematical Programming, Vol. 5, No. 1
- Two new algorithms for minimal cost flow problems
  Computing, Vol. 11, No. 3
- Technical Contributions Finding Negative Cycles *
  25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 11, No. 1
- Networks of Flow
- On the equivalence between the Node‐ARC and ARC‐Chain formulations for the multi‐commodity maximal flow problem
  29 October 2013 | Naval Research Logistics Quarterly, Vol. 16, No. 4
- A maximum utility solution to a vehicle constrained tanker scheduling problem
  29 October 2013 | Naval Research Logistics Quarterly, Vol. 15, No. 3

Volume 14, Issue 3

November 1967

Pages 127-261

Article Information

Metrics

Information

Published Online:November 01, 1967

Cite as

Morton Klein, (1967) A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems. Management Science 14(3):205-220.

https://doi.org/10.1287/mnsc.14.3.205

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems

Abstract

Volume 14, Issue 3

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News