A Primal Partitioning Solution for the Arc-Chain Formulation of a Multicommodity Network Flow Problem

Judith M. Farvolden, Warren B. Powell and Irvin J. Lustig
Additional contact information
Judith M. Farvolden: University of Toronto, Toronto, Ontario, Canada
Warren B. Powell: Princeton University, Princeton, New Jersey
Irvin J. Lustig: Princeton University, Princeton, New Jersey

Operations Research, 1993, vol. 41, issue 4, 669-693

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.

Keywords: industries; transportation/shipping: transshipment and consolidation problems; networks/graphs; multicommodity: primal partitioning solution; programming; linear; large-scale systems: multicommodity network flow problems (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.4.669 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:41:y:1993:i:4:p:669-693

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().