Minimum-Cost Multicommodity Network Flows

J. A. Tomlin
J. A. Tomlin
University of Adelaide, Adelaide, South Australia
Search for more papers by this author

University of Adelaide, Adelaide, South Australia

Published Online:1 Feb 1966https://doi.org/10.1287/opre.14.1.45

Abstract

The minimum-cost multicommodity network flow problem is formulated in both node-arc and arc-chain form, leading to very large linear programs. The special structure of these programs is utilized in algorithms for their solution.

Cited by
- Shadow-price-guided capacity governance in electric-vehicle battery reverse logistics: a hypergraph optimal transport study
  Transportation Research Part E: Logistics and Transportation Review, Vol. 210
- Lexicographic column generation with a tree search pricing algorithm
  20 February 2026 | Mathematical Methods of Operations Research, Vol. 19
- Integrating Intra-terminal Logistics Optimization and Freight Train Scheduling
  19 July 2025
- Quantum Network Routing Based on Surface Code Error Correction
- Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport
  Isabel Haasler,
  Axel Ringh,
  Yongxin Chen,
  Johan Karlsson
  15 June 2023 | Mathematics of Operations Research, Vol. 49, No. 2
- Phase transitions of the price-of-anarchy function in multi-commodity routing games
  Transportation Research Part B: Methodological, Vol. 182
- The price of anarchy in routing games as a function of the demand
  8 September 2021 | Mathematical Programming, Vol. 203, No. 1-2
- Modeling and solving a corporate vehicle-sharing problem combined with other modes of transport
  EURO Journal on Transportation and Logistics, Vol. 13
- Quickest Multi‐Commodity Contraflow with Non‐Symmetric Traversal Times
  11 July 2023
- Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport
  15 June 2023 | Mathematics of Operations Research, Vol. 23
- Multi-commodity flow problem on lossy network with partial lane reversals
  6 February 2023 | Annals of Operations Research, Vol. 323, No. 1-2
- TraVaS: Differentially Private Trace Variant Selection for Process Mining
  26 March 2023
- Optimised Use of Fixed-Scheduled Container Trains in Collaborative Logistics
  Transportation Research Procedia, Vol. 72
- The multicommodity network flow problem: state of the art classification, applications, and solution methods
  23 April 2020 | Operational Research, Vol. 22, No. 1
- Dynamic Multicommodity Contraflow Problem with Asymmetric Transit Times
  Journal of Applied Mathematics, Vol. 2022
- Optimal Steering of Ensembles With Origin-Destination Constraints
  IEEE Control Systems Letters, Vol. 5, No. 3
- Modeling the Cost of Flexibility in Communication Networks
- Scheduling Inter-Datacenter Video Flows for Cost Efficiency
  IEEE Transactions on Services Computing, Vol. 14, No. 3
- Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals
  International Journal of Mathematics and Mathematical Sciences, Vol. 2020
- An Improved Flow Deviation Method for the Maximum Concurrent Flow Problem
- Spare Capacity Dimensioning for different Re-Routing Strategies in Transport Networks
- A decomposition scheme for parallelization of system optimal dynamic traffic assignment on urban networks with multiple origins and destinations
  Computer-Aided Civil and Infrastructure Engineering, Vol. 34, No. 10
- Network Flow Models
- Bibliography
- Distributed Service Function Chaining
  IEEE Journal on Selected Areas in Communications, Vol. 35, No. 11
- On solving multi-commodity flow problems: An experimental evaluation
  Chinese Journal of Aeronautics, Vol. 30, No. 4
- A multi-commodity network flow-based formulation for the multi-period cell formation problem
  18 November 2016 | The International Journal of Advanced Manufacturing Technology, Vol. 91, No. 1-4
- A penalty-based scaling algorithm for the multi-period multi-product distribution planning problem
  27 July 2016 | Engineering Optimization, Vol. 49, No. 4
- The Weighted Uncapacitated Planned Maintenance Problem
  9 November 2016
- Uncertain minimum cost multicommodity flow problem
  15 September 2015 | Soft Computing, Vol. 21, No. 1
- User-Network Cooperation-Based Sleep Scheduling for Communication Networks
  IEEE Journal on Selected Areas in Communications, Vol. 34, No. 12
- Fixed‐route taxi system: route network design and fleet size minimization problems
  6 October 2016 | Journal of Advanced Transportation, Vol. 50, No. 6
- Node Dependency in Multi-Commodity Flow Problem with Applications to Transportation Networks
  29 June 2016
- Finding feasible solutions for multi-commodity flow problems
- A disaster evacuation network model for transporting multiple priority evacuees
  28 April 2015 | IIE Transactions, Vol. 47, No. 11
- Time-dependent optimization of a multi-item uncertain supply chain network: A hybrid approximation algorithm
  Discrete Optimization, Vol. 18
- A minimum cost network flow model for the maximum covering and patrol routing problem
  European Journal of Operational Research, Vol. 247, No. 1
- A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem
  European Journal of Operational Research, Vol. 244, No. 2
- Hybrid Algorithm for Route Design on Bus Rapid Transit Systems
  Jose L. Walteros,
  Andrés L. Medaglia,
  Germán Riaño
  14 August 2013 | Transportation Science, Vol. 49, No. 1
- The Two-Commodity Capacitated Vehicle Routing Problem with Synchronization
  IFAC-PapersOnLine, Vol. 48, No. 3
- Decentralized RSU-based real-time path planning for vehicular ad hoc networks
- A MIP model for scheduling India’s General elections and police movement
  17 September 2013 | OPSEARCH, Vol. 51, No. 4
- Multipath Routing from a Traffic Engineering Perspective: How Beneficial Is It?
- Flow Deviation: 40years of incremental flows for packets, waves, cars and tunnels
  Computer Networks, Vol. 66
- Symbiotic network design strategies in the presence of coexisting transportation networks
  Transportation Research Part B: Methodological, Vol. 62
- Decision support for vehicle configuration determination in Inter Terminal Transport system design
- A novel hybrid-link-based container routing model
  Transportation Research Part E: Logistics and Transportation Review, Vol. 61
- Dynamic adaptive anti-jamming via controlled mobility
- Network Configuration in Presence of Synchronization Requirements
  14 December 2012
- A Branch, Price and Cut Approach for Optimal Traffic Grooming in WDM Optical Networks
- Bibliography
  15 August 2011
- System Reliability Evaluation for a Multistate Supply Chain Network With Failure Nodes Using Minimal Paths
  IEEE Transactions on Reliability, Vol. 58, No. 1
- Efficient Traffic Grooming Scheme for WDM Network
- An extended model and a column generation algorithm for the planar multicommodity flow problem
  16 April 2007 | Networks, Vol. 50, No. 1
- Reliability of a computer network in case capacity weight varying with arcs, nodes and types of commodity
  Reliability Engineering & System Safety, Vol. 92, No. 5
- Reliability Evaluation for an Information Network With Node Failure Under Cost Constraint
  IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, Vol. 37, No. 2
- On routing in large WDM networks
  Optical Switching and Networking, Vol. 3, No. 3-4
- Optimization-based decision support for order promising in supply chain networks
  International Journal of Production Economics, Vol. 103, No. 1
- A retrospective on Beckmann, McGuire and Winsten's Studies in the Economics of Transportation
  Papers in Regional Science, Vol. 84, No. 1
- Approximation algorithms for traffic routing in wavelength routed WDM networks
- An Efficient Algorithm for Routing in WDM Networks
- An algorithm to evaluate the system reliability for multicommodity case under cost constraint
  Computers & Mathematics with Applications, Vol. 48, No. 5-6
- Capacitated multicommodity network flow problems with piecewise linear concave costs
  IIE Transactions, Vol. 36, No. 7
- An Augmented Lagrangian Algorithm for Large Scale Multicommodity Routing
  Computational Optimization and Applications, Vol. 27, No. 2
- BIBLIOGRAPHY
- A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation
  Kaj Holmberg,
  Di Yuan,
  1 February 2003 | INFORMS Journal on Computing, Vol. 15, No. 1
- ON THE MULTICOMMODITY RELIABILITY FOR A STOCHASTIC- FLOW NETWORK WITH NODE FAILURE UNDER BUDGET CONSTRAINT
  Journal of the Chinese Institute of Industrial Engineers, Vol. 20, No. 1
- Reliability evaluation for a multi‐commodity flow model under budget constraint
  Journal of the Chinese Institute of Engineers, Vol. 25, No. 1
- The freight routing problem of time-definite freight delivery common carriers
  Transportation Research Part B: Methodological, Vol. 35, No. 6
- Routing in wavelength routed optical networks
- ON A MULTICOMMODITY FLOW NETWORK RELIABILITY MODEL AND ITS APPLICATION TO A CONTAINER-LOADING TRANSPORTATION PROBLEM
  Journal of the Operations Research Society of Japan, Vol. 44, No. 4
- 機率性負載量與預算限制下求算多種商品利用貨櫃運輸之可靠度問題
  Journal of the Chinese Institute of Industrial Engineers, Vol. 16, No. 5
- Progress Made in Solving the Multicommodity Flow Problem
  SIAM Journal on Optimization, Vol. 8, No. 4
- Advances in Solving the Multicommodity-Flow Problem
  Richard D. McBride,
  1 April 1998 | Interfaces, Vol. 28, No. 2
- A design methodology for fractal layout organization
  IIE Transactions, Vol. 29, No. 10
- A Lagrangean Relaxation Scheme for Structured Linear Programs With Application To Multicommodity Network Flows
  20 March 2007 | Optimization, Vol. 40, No. 3
- An augmented lagrangean dual algorithm for link capacity side constrained traffic assignment problems
  Transportation Research Part B: Methodological, Vol. 29, No. 6
- Network Problems
- A column generation and partitioning approach for multi-commodity flow problems
  Telecommunication Systems, Vol. 3, No. 3
- A model management solution system for multicommodity network flows
  European Journal of Operational Research, Vol. 71, No. 3
- Minimum concave-cost network flow problems: Applications, complexity, and algorithms
  Annals of Operations Research, Vol. 25, No. 1
- The stochastic multicommodity flow problem
  11 October 2006 | Networks, Vol. 20, No. 2
- Distribution Requirements Planning: A Generalised System for Delivery Scheduling in a Multi‐Sourcing Logistics System
  International Journal of Physical Distribution & Logistics Management, Vol. 20, No. 2
- Graph Algorithms
- NETWORK EQUILIBRIUM MODELS OF URBAN LOCATION AND TRAVEL CHOICES: A RETROSPECTIVE SURVEY*
  28 July 2006 | Journal of Regional Science, Vol. 28, No. 2
- On the selection of primary paths for a communication network
  Computer Networks and ISDN Systems, Vol. 9, No. 4
- Network Design with Multiple Demand: A New Approach
- Multi‐source‐sink pairs connection in a network and its heuristic algorithm
  12 September 2008 | Electronics and Communications in Japan (Part I: Communications), Vol. 65, No. 5
- The simplex SON algorithm for LP/embedded network problems
  25 February 2009
- Dynamic model for long-term expansion planning studies of power transmission systems: the Ortie model
  International Journal of Electrical Power & Energy Systems, Vol. 3, No. 1
- Optimum Synthesis of a Network with Non-Simultaneous Multicommodity Flow Requirements
- Investment in stochastic minimum cost generalized multicommodity networks with application to coal transport
  11 October 2006 | Networks, Vol. 10, No. 4
- Maximization Of The Vector-Flow In Multigommodity Networks
  25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 17, No. 3
- Queuing effects in the solution of constrained store-and-forward network flow problems
  27 April 2007 | International Journal of Systems Science, Vol. 10, No. 7
- Multicommodity network flows—A survey
  11 October 2006 | Networks, Vol. 8, No. 1
- An infeasibility pricing algorithm for the multicommodity minimum cost flow problem
  Computers & Operations Research, Vol. 5, No. 4
- Modèle dynamique d'optimisation à long terme d'un réseau de transport d'énergie électrique
  29 March 2011 | RAIRO - Operations Research, Vol. 12, No. 2
- A product form representation of the inverse of a multicommodity cycle matrix
  11 October 2006 | Networks, Vol. 7, No. 4
- Optimization Models of Transportation Network Improvement
  1 October 1977 | Progress in Human Geography, Vol. 1, No. 3
- Solving multicommodity transportation problems using a primal partitioning simplex technique
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 24, No. 2
- A generalized upper bounding approach to a communications network planning problem
  11 October 2006 | Networks, Vol. 7, No. 1
- Problems in Computer Network Optimalization
- Multiflots de coût minimal avec fonctions de coût concaves
  Annales Des Télécommunications, Vol. 31, No. 3-4
- Centralization and decentralization of decision-making in transportation networks
  1 February 1976 | ACM SIGMAP Bulletin, No. 20
- Optimisation et Planification des Reseaux de Telecommunications
  21 May 2005
- A minimum‐cost multicommodity network flow problem concerning imports and exports
  11 October 2006 | Networks, Vol. 5, No. 4
- Heuristic Algorithms for Solving a Large Scale Multicommodity Flow Problem on a Network with a Step Function Cost
  28 September 2015 | Studies in Applied Mathematics, Vol. 54, No. 3
- 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
- On the Traffic Handling Capability of Communication Networks Homogeneously Loaded
  11 October 2006 | Networks, Vol. 5, No. 2
- Résolution des problèmes de multiflots en nombres entiers dans les grands réseaux
  29 March 2011 | Revue française d'automatique, informatique, recherche opérationnelle. Recherche opérationnelle, Vol. 9, No. V3
- Configuring a transportation route network via the method of successive approximation
  Computers & Operations Research, Vol. 1, No. 3-4
- A generalized chain labelling algorithm for solving multicommodity flow problems
  Computers & Operations Research, Vol. 1, No. 3-4
- Planification a court et a moyen terme d’un réseau de télécommunications
  Annales Des Télécommunications, Vol. 29, No. 11-12
- Transport network optimization in the Dutch integral transportation study
  Transportation Research, Vol. 8, No. 1
- On building minimum cost communication networks over time
  11 October 2006 | Networks, Vol. 4, No. 1
- An algorithm for nonlinear multicommodity flow problems
  11 October 2006 | Networks, Vol. 4, No. 4
- A Two-Stage Decomposition Algorithm For A Generalized Multi-Commodity Flow Problem
  25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 11, No. 3
- On Optimal Routing Through Communication Nets
  IEEE Transactions on Communications, Vol. 21, No. 8
- The flow deviation method: An approach to store‐and‐forward communication network design
  2 March 2007 | Networks, Vol. 3, No. 2
- On building minimum cost communication networks
  11 October 2006 | Networks, Vol. 3, No. 4
- A partitioning algorithm for the multicommodity network flow problem
  Mathematical Programming, Vol. 3-3, No. 1
- Towards a more rational airline route structure: An optimization approach
- Evaluation of Optimal Routing Policies in Communication Nets by Simulation
  IEEE Transactions on Communications, Vol. 20, No. 3
- The multicommodity network flow model revised to include vehicle per time period and node constraints
  1 August 2006 | Naval Research Logistics Quarterly, Vol. 19, No. 1
- Traffic control and highway networks
  9 March 2007 | Networks, Vol. 2, No. 2
- CHAPTER III EXTREMAL PRINCIPLES AND TRAFFIC ASSIGNMENT
- Minimum cost routing for static network models
  11 October 2006 | Networks, Vol. 1, No. 2
- Multicommodity networks with resource constraints: The generalized multicommodity flow problem
  6 November 2006 | Networks, Vol. 1, No. 3
- Investment in network expansion under uncertainty
  Transportation Research, Vol. 4, No. 3
- 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
- Analysis and design of communication networks with memory
  Journal of the Franklin Institute, Vol. 287, No. 1
- Recent Advances in Network Flows
  SIAM Review, Vol. 10, No. 3

Volume 14, Issue 1

January-February 1966

Pages 1-187

Article Information

Metrics

Information

Published Online:February 01, 1966

Cite as

J. A. Tomlin, (1966) Minimum-Cost Multicommodity Network Flows. Operations Research 14(1):45-51.

https://doi.org/10.1287/opre.14.1.45

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Minimum-Cost Multicommodity Network Flows

Abstract

Volume 14, Issue 1

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News