Primal partitioning solution for the arc-chain formulation of a multicommodity network flow problem

Judith M. Farvolden, Warren Buckler Powell, Irvin J. Lustig

Research output: Contribution to journalArticlepeer-review

39 Scopus citations

Abstract

We present a new solution approach for the multicommodity network flow problem (MCNF) based upon both primal partitioning and decomposition techniques, which simplifies the computations required by the simplex method. The partitioning is performed on an arc-chain incidence matrix of the MCNF, similar within a change of variables to the constraint matrix of the master problem generated in a Dantzig-Wolfe decomposition, to isolate a very sparse, near-triangular working basis of greatly reduced dimension. The majority of the simplex operations performed on the partitioned basis are simply additive and network operations specialized for the nine possible pivot types identified. The columns of the arc-chain incidence matrix are generated by a dual network simplex method for updating shortest paths when link costs change.

Original languageEnglish (US)
Pages (from-to)669-693
Number of pages25
JournalOperations Research
Volume41
Issue number4
DOIs
StatePublished - Jan 1 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Primal partitioning solution for the arc-chain formulation of a multicommodity network flow problem'. Together they form a unique fingerprint.

Cite this