A Survey of Linear Cost Multicommodity Network Flows

Jeff L. Kennington
Jeff L. Kennington
Southern Methodist University, Dallas, Texas
Search for more papers by this author

Southern Methodist University, Dallas, Texas

Published Online:1 Apr 1978https://doi.org/10.1287/opre.26.2.209

Abstract

This exposition presents a state-of-the-art survey of results and algorithms for linear multicommodity network flow problems.

Cited by
- Distributionally Robust Chance-Constrained Multicommodity Network Flow Problem in Dynamic Networks: A Column-Generation Approach
  9 March 2026 | Operations Research Forum, Vol. 7, No. 1
- Accelerated Approximate Optimization of Multi-commodity Flows on Directed Graphs
  15 June 2025
- Advanced Optimization Models for Bandwidth Provisioning and Routing in Fixed Microwave Backhaul Networks
  19 February 2025 | Transport and Telecommunication Journal, Vol. 26, No. 1
- Eliminating Bottlenecks in MANETs
- 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
- 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
- Decision Support System for Feasibility Study and Determination the Optimal Way to Increase the Throughput Capacity of Main Oil Pipelines
- Deterministic Container-to-Mode Assignment
  6 October 2022
- Time-sensitive Multi-Flow Routing in Highly Utilized MANETs
- Flows of Substances in Networks and Network Channels: Selected Results and Applications
  18 October 2022 | Entropy, Vol. 24, No. 10
- Network Design with Service Requirements: Scaling-up the Size of Solvable Problems
  Naga V. C. Gudapati,
  Enrico Malaguti,
  Michele Monaci
  5 May 2022 | INFORMS Journal on Computing, Vol. 34, No. 5
- 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
- Variable fixing heuristics for the capacitated multicommodity network flow problem with multiple transport lines, a heterogeneous fleet and time windows
  1 September 2020 | Transportation Letters, Vol. 14, No. 2
- An analytical solution to the multicommodity network flow problem with weighted random routing
  16 June 2021 | Applied Network Science, Vol. 6, No. 1
- Maximum Multi-Commodity Flow with Proportional and Flow-Dependent Capacity Sharing
  26 September 2021
- Maximum Multicommodity Flow with Intermediate Storage
  Mathematical Problems in Engineering, Vol. 2021
- Optimal Steering of Ensembles With Origin-Destination Constraints
  IEEE Control Systems Letters, Vol. 5, No. 3
- Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals
  International Journal of Mathematics and Mathematical Sciences, Vol. 2020
- Models and algorithms for network design in urban freight distribution systems
  Transportation Research Procedia, Vol. 47
- Glossary of Mathematical Optimization Terminology
- Efficient Infrastructure Restoration Strategies Using the Recovery Operator
  28 November 2017 | Computer-Aided Civil and Infrastructure Engineering, Vol. 32, No. 12
- Analysis of budget for interdiction on multicommodity network flows
  1 March 2016 | Journal of Global Optimization, Vol. 67, No. 3
- Multicommodity Flow Problems with Commodity Compatibility Relations
  8 November 2017 | ITM Web of Conferences, Vol. 14
- A survey of optimization algorithms for wireless sensor network lifetime maximization
  Computers & Industrial Engineering, Vol. 101
- Fixed‐route taxi system: route network design and fleet size minimization problems
  6 October 2016 | Journal of Advanced Transportation, Vol. 50, No. 6
- The Interdependent Network Design Problem for Optimal Infrastructure System Restoration
  4 December 2015 | Computer-Aided Civil and Infrastructure Engineering, Vol. 31, No. 5
- Deadline-aware advance reservation scheduling algorithms for media production networks
  Computer Communications, Vol. 77
- Single-path versus multi-path advance reservation in media production networks
- Optimization and sustainable development
  26 August 2014 | Computational Management Science, Vol. 12, No. 3
- A multi-start variable neighborhood search for solving the single path multicommodity flow problem
  Applied Mathematics and Computation, Vol. 251
- Analysis of a system of nonlocal conservation laws for multi-commodity flow on networks
  Networks & Heterogeneous Media, Vol. 10, No. 4
- A MIP model for scheduling India’s General elections and police movement
  17 September 2013 | OPSEARCH, Vol. 51, No. 4
- A novel approach for designing rental vehicle repositioning strategies
  3 June 2014 | IIE Transactions, Vol. 46, No. 9
- General Bibliography
  8 August 2014
- A Model for the Design of a Minimum‐cost Telecommunications Network
  8 August 2014
- A simulated annealing based heuristic for the multi-source single-path multi-commodity network flow problem
- Algorithms for an Integer Multicommodity Network Flow Problem with Node Reliability Considerations
  8 August 2013 | Journal of Optimization Theory and Applications, Vol. 161, No. 2
- Linear Capacity and Heuristic Algorithms for Multicommodity Flow in Computer Networks Engineering
  1 September 2013 | Advanced Materials Research, Vol. 787
- Integrated job scheduling and network routing
  28 August 2012 | Networks, Vol. 61, No. 3
- Generating maximal efficient faces for the multiobjective multicommodity flow problem
- Resource Allocation, Transmission Coordination and User Association in Heterogeneous Networks: A Flow-Based Unified Approach
  IEEE Transactions on Wireless Communications, Vol. 12, No. 3
- A Model for the Design of a Minimum‐Cost Telecommunications Network
  13 February 2013
- Multicommodity Network Flows
  23 January 2016
- Model for Network Assignment Problem of Capacitated Freight with Disruptions
  1 January 2012 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 2269, No. 1
- An ant colony optimization metaheuristic for solving bi-objective multi-sources multicommodity communication flow problem
- A two-phase heuristic algorithm for the fixed-charge capacitated network design problem with turn penalties
  KSCE Journal of Civil Engineering, Vol. 15, No. 6
- Lagrangian relaxation heuristics for deterministic transshipment problems
  Journal of the Chinese Institute of Industrial Engineers, Vol. 28, No. 4
- Adaptive memory in multistart heuristics for multicommodity network design
  23 March 2010 | Journal of Heuristics, Vol. 17, No. 2
- Multicommodity Flows
  14 January 2011
- An Introduction to Integer and Large-Scale Linear Optimization
  30 October 2010
- A linear model for compound multicommodity network flow problems
  Computers & Operations Research, Vol. 37, No. 6
- Power-efficient radio configuration in fixed broadband wireless networks
  Computer Communications, Vol. 33, No. 8
- Minimizing energy consumption by power-efficient radio configuration in fixed broadband wireless networks
- Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios
  Omega, Vol. 36, No. 6
- A novel modeling approach for express package carrier planning
  25 August 2008 | Naval Research Logistics (NRL), Vol. 55, No. 7
- Multicommodity Flow Problems
- On Shortest Path Representation
  IEEE/ACM Transactions on Networking, Vol. 15, No. 6
- An extended model and a column generation algorithm for the planar multicommodity flow problem
  16 April 2007 | Networks, Vol. 50, No. 1
- End-to-end delay margin balancing approach for routing in multi-class networks
  3 July 2006 | Wireless Networks, Vol. 13, No. 3
- Integration of the Load-Matching and Routing Problem with Equipment Balancing for Small Package Carriers
  Amy Cohn,
  Sarah Root,
  Alex Wang,
  Douglas Mohr,
  1 May 2007 | Transportation Science, Vol. 41, No. 2
- Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly
  Applied Mathematics and Computation, Vol. 188, No. 1
- Chapter 5 Dynamic Models for Freight Transportation
- Algorithms for discrete and continuous multicommodity flow network interdiction problems
  IIE Transactions, Vol. 39, No. 1
- Dynamic Decision Making for Less-Than-Truckload Trucking Operations
  1 January 2007 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 2032, No. 1
- Dynamic-Programming Approximations for Stochastic Time-Staged Integer Multicommodity-Flow Problems
  Huseyin Topaloglu,
  Warren B. Powell,
  1 February 2006 | INFORMS Journal on Computing, Vol. 18, No. 1
- On Improving the Accuracy of OSPF Traffic Engineering
- Multicommodity Network Flow Models and Algorithms in Telecommunications
- Real-Time Mass Passenger Transport Network Optimization Problems
  1 January 2006 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 1964, No. 1
- A multistage benders decomposition method for production planning problems with approved vendor matrices
  Journal of Manufacturing Systems, Vol. 24, No. 4
- Delay Satisfaction End-to-End Priority Assignment and Routing in Multi- Class Priority Networks
- A Distributed Algorithm for Path Restoration in Circuit Switched Communication Networks
- A decomposition approach for an equipment selection and multiple product routing problem incorporating environmental factors
  European Journal of Operational Research, Vol. 156, No. 3
- 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
- Meta Research in OR/MS: A Taxonomy, Bibliography and Classification of the Literature
  SSRN Electronic Journal, Vol. 8
- 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
- A Concavity Result for Network Design Problems
  Journal of Global Optimization, Vol. 24, No. 1
- Bounds and Heuristics for the Shortest Capacitated Paths Problem
  Journal of Heuristics, Vol. 8, No. 4
- Models for the design and analysis of a large package sort facility
  29 January 2002 | Networks, Vol. 39, No. 2
- Network Design for Express Shipment Delivery
  Computational Optimization and Applications, Vol. 21, No. 3
- Scheduling railway freight delivery appointments using a bid price approach
  Transportation Research Part A: Policy and Practice, Vol. 36, No. 2
- D.C. programming approach for multicommodity network optimization problems with step increasing cost functions
  Journal of Global Optimization, Vol. 22, No. 1-4
- A family of algorithms for network reliability problems
- Discrete Cost Multicommodity Network Optimization Problems and Exact Solution Methods
  Annals of Operations Research, Vol. 106, No. 1-4
- Constraint Generation for Network Reliability Problems
  Annals of Operations Research, Vol. 106, No. 1-4
- The Path Restoration Version of the Spare Capacity Allocation Problem with Modularity Restrictions: Models, Algorithms, and an Empirical Analysis
  Jeffery L. Kennington,
  Mark W. Lewis,
  1 August 2001 | INFORMS Journal on Computing, Vol. 13, No. 3
- Multicommodity Flow Problems
- Multicommodity network flows
  25 October 2005
- A Simplex-Based Tabu Search Method for Capacitated Network Design
  Teodor Gabriel Crainic,
  Michel Gendreau,
  Judith M. Farvolden,
  1 August 2000 | INFORMS Journal on Computing, Vol. 12, No. 3
- Comparison of some algorithms for manufacturing production planning
  IFAC Proceedings Volumes, Vol. 33, No. 20
- A Survey of Algorithms for Convex Multicommodity Flow Problems
  A. Ouorou,
  P. Mahey,
  J.-Ph. Vial,
  1 January 2000 | Management Science, Vol. 46, No. 1
- A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems
  Antonio Frangioni,
  Giorgio Gallo,
  1 November 1999 | INFORMS Journal on Computing, Vol. 11, No. 4
- Multimodal Express Package Delivery: A Service Network Design Application
  Daeki Kim,
  Cynthia Barnhart,
  Keith Ware,
  Gregory Reinhardt,
  1 November 1999 | Transportation Science, Vol. 33, No. 4
- Exact solution of multicommodity network optimization problems with general step cost functions
  Operations Research Letters, Vol. 25, No. 1
- On Extended Models of Multicommodity Routing with Side Constraints on Paths
- Progress Made in Solving the Multicommodity Flow Problem
  SIAM Journal on Optimization, Vol. 8, No. 4
- 對偶陡升法求解多貨品有界網路流量問題
  30 March 2012 | Journal of the Chinese Institute of Industrial Engineers, Vol. 15, No. 4
- Advances in Solving the Multicommodity-Flow Problem
  Richard D. McBride,
  1 April 1998 | Interfaces, Vol. 28, No. 2
- A Scaling Algorithm for Multicommodity Flow Problems
  Rina R. Schneur,
  James B. Orlin,
  1 April 1998 | Operations Research, Vol. 46, No. 2
- Network dual steepest-edge methods for solving capacitated multicommodity network problems
  Computers & Industrial Engineering, Vol. 33, No. 3-4
- Testing and evaluation of a multi‐commodity multi‐modal network flow model for disaster relief management
  19 January 2010 | Journal of Advanced Transportation, Vol. 31, No. 3
- Multicommodity network flow with jump constraints
  Discrete Mathematics, Vol. 165-166
- A Lagrangean Relaxation Scheme for Structured Linear Programs With Application To Multicommodity Network Flows
  20 March 2007 | Optimization, Vol. 40, No. 3
- M
- A heuristic solution procedure for multicommodity integer flows
  Computers & Operations Research, Vol. 22, No. 10
- A smooth penalty function algorithm for network-structured problems
  European Journal of Operational Research, Vol. 83, No. 1
- The minimal average cost flow problem
  European Journal of Operational Research, Vol. 81, No. 3
- Basis characterisation for linear multicommodity network programs
  Optimization, Vol. 33, No. 4
- PARALLELIZATION STRATEGIES OF A ROW-ACTION METHOD FOR MULTICOMMODITY NETWORK FLOW PROBLEMS
  Parallel Algorithms and Applications, Vol. 6, No. 2-3
- An approach for fuzzy linear multicommodity transportation problems and its application
- Allocation and routing of mobile computed tomography equipment
  Socio-Economic Planning Sciences, Vol. 28, No. 4
- A data-level parallel linear-quadratic penalty algorithm for multicommodity network flows
  1 December 1994 | ACM Transactions on Mathematical Software, Vol. 20, No. 4
- A column generation and partitioning approach for multi-commodity flow problems
  Telecommunication Systems, Vol. 3, No. 3
- Dynamic factorization in large-scale optimization
  Mathematical Programming, Vol. 64, No. 1-3
- Proximal decomposition for multicommodity flow problems with convex costs
  Telecommunication Systems, Vol. 3, No. 1
- A knowledge-based operation support system for network traffic management
  Decision Support Systems, Vol. 11, No. 1
- PRODUCTION SCHEDULING IN A FLEXIBLE MANUFACTURING SYSTEM WITH SETUPS
  IIE Transactions, Vol. 25, No. 5
- ALLOCATING AND SCHEDULING MOBILE DIAGNOSTIC IMAGING EQUIPMENT AMONG HOSPITALS
  1 September 1993 | Production and Operations Management, Vol. 2, No. 3
- Dual-ascent methods for large-scale multicommodity flow problems
  Naval Research Logistics, Vol. 40, No. 3
- An implementation of a parallel primal-dual interior point method for block-structured linear programs
  Computational Optimization and Applications, Vol. 1, No. 2
- MICAH: a genetic algorithm system for multi-commodity transshipment problems
- Reducing air traffic delay in a space-time network
- On the Fine-Grain Decomposition of Multicommodity Transportation Problems
  SIAM Journal on Optimization, Vol. 1, No. 4
- Route selection on freight networks with weight and volume constraints
  Transportation Research Part B: Methodological, Vol. 25, No. 4
- Analysis of relaxations for the multi-item capacitated lot-sizing problem
  1 December 1990 | Annals of Operations Research, Vol. 26, No. 1-4
- Multicommodity flows in certain planar directed networks
  Discrete Applied Mathematics, Vol. 27, No. 1-2
- The stochastic multicommodity flow problem
  11 October 2006 | Networks, Vol. 20, No. 2
- Graph Algorithms
- A survey of dynamic network flows
  Annals of Operations Research, Vol. 20, No. 1
- Networks synthesis and optimum network design problems: Models, solution methods and applications
  11 October 2006 | Networks, Vol. 19, No. 3
- Chapter II Linear programming
- Chapter IV Network flows
- Network models for seat allocation on flights
  Transportation Research Part B: Methodological, Vol. 22, No. 4
- Direct versus terminal freight routing on a network with concave costs
  Transportation Research Part B: Methodological, Vol. 21, No. 4
- Network Synthesis and Dynamic Network Optimization
- A fertilizer transportation problem
  Zeitschrift für Operations Research, Vol. 30, No. 6
- The multiperiod assignment problem: A multicommodity network flow model and specialized branch and bound algorithm
  European Journal of Operational Research, Vol. 23, No. 3
- Analyzing trade-offs between transportation, inventory and production costs on freight networks
  Transportation Research Part B: Methodological, Vol. 19, No. 5
- Network Design with Multiple Demand: A New Approach
- On multicommodity flows in planar graphs
  11 October 2006 | Networks, Vol. 14, No. 2
- A k -SHORTEST PATHS ROUTING HEURISTIC FOR STOCHASTIC NETWORK EVACUATION MODELS
  21 May 2007 | Engineering Optimization, Vol. 7, No. 4
- Large-scale linear programming: Geometry, working bases and factorizations
  Mathematical Programming, Vol. 26, No. 1
- Some multicommodity transport problems reducible to a single-commodity problem
  USSR Computational Mathematics and Mathematical Physics, Vol. 22, No. 1
- Generalizations of Hoffman's existence theorem for circulations
  11 October 2006 | Networks, Vol. 11, No. 3
- Optimal planning of network structures within an exchange area
  European Journal of Operational Research, Vol. 7, No. 1
- MAPUM: A model for assigning passengers to a flight schedule
  Transportation Research Part A: General, Vol. 15, No. 2
- Current and future research directions in network optimization
  Computers & Operations Research, Vol. 8, No. 2
- 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
- The dynamic transportation problem: A survey
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 27, No. 1
- Reducing computational effort in detecting integral multicommodity networks
  Computers & Operations Research, Vol. 7, No. 4
- Vulnerability Analysis of Multiterminal Distribution Systems and Networks
  IFAC Proceedings Volumes, Vol. 13, No. 11
- Vulnerability and Structural Perturbations of Network Flow Systems
  IFAC Proceedings Volumes, Vol. 13, No. 6
- Distributionsplanung

Volume 26, Issue 2

March-April 1978

Pages 209-376

Article Information

Metrics

Information

Published Online:April 01, 1978

Cite as

Jeff L. Kennington, (1978) A Survey of Linear Cost Multicommodity Network Flows. Operations Research 26(2):209-236.

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

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Survey of Linear Cost Multicommodity Network Flows

Abstract

Volume 26, Issue 2

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News