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

72 Scopus citations

Abstract

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
Volume62
Issue number1-3
DOIs
StatePublished - Feb 1 1993

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Mathematics(all)
  • Safety, Risk, Reliability and Quality
  • Management Science and Operations Research
  • Software
  • Computer Graphics and Computer-Aided Design
  • Computer Science(all)

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

Cite this