Monotonicity and conformality in multicommodity network‐flow problems

Journal Article

Abstract The objective of this paper is to develop a monotonicity theory for the important class of minimum convex‐cost parametric multicommodity network‐flow problems defined over directed graphs. The results allow us to determine when it is possible to predict, without numerical computations, the direction of change of optimal multicommodity flows resulting from changes in arc‐commodity parameters. In particular, we provide necessary and sufficient conditions that for every cost function satisfying some convexity and submodularity assumptions there always exists an optimal multicommodity flow for which the flow of a commodity in a given arc a is nondecreasing (resp., nonincreasing) in the parameter of a distinct commodity in arc b. These conditions are that either (1) there are only two commodities and the underlying undirected graph is series‐parallel or (2) there are three or more commodities and the graph is 2‐isomorphic to a suspension graph. A characterization of the precise pairs of arcs for which the above monotonicity result holds is also provided.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.