Multicommodity network flows: The impact of formulation on decomposition

Kim L. Jones, Irvin J. Lustig, Judith M. Farvolden, Warren Buckler Powell

Research output: Contribution to journalArticlepeer-review

74 Scopus citations


This paper investigates the impact of problem formulation on Dantzig-Wolfe decomposition for the multicommodity network flow problem. These problems are formulated in three ways: origin-destination specific, destination specific, and product specific. The path-based origin-destination specific formulation is equivalent to the tree-based destination specific formulation by a simple transformation. Supersupply and superdemand nodes are appended to the tree-based product specific formulation to create an equivalent path-based product specific formulation. We show that solving the path-based problem formulations by decomposition results in substantially fewer master problem iterations and lower CPU times than by using decomposition on the equivalent tree-based formulations. Computational results on a series of multicommodity network flow problems are presented.

Original languageEnglish (US)
Pages (from-to)95-117
Number of pages23
JournalMathematical Programming
Issue number1-3
StatePublished - Feb 1993

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Multicommodity network flows: The impact of formulation on decomposition'. Together they form a unique fingerprint.

Cite this