IDEAS home Printed from
   My bibliography  Save this article

Parallel Decomposition of Multicommodity Network Flows Using a Linear-Quadratic Penalty Algorithm


  • Mustafa C. Pinar

    (Institute for Numerical Analysis, The Technical University of Denmark, 2800 Lyngby, Denmark)

  • Stavros A. Zenios

    (Decision Sciences Department, The Wharton School, University of Pennsylvania, Philadelphia, PA 19104)


The central theme of this paper is the design and evaluation of a parallel decomposition algorithm for multicommodity network flow problems based on the notion of piecewise linear-quadratic penalty (LQP) functions. The algorithm induces separability of both the constraint set and the objective function by commodity during the subproblem phase. Hence it is suitable for implementations on coarse grain parallel architectures. A master problem, of significantly smaller dimension than the original problem, uses dense linear algebra computations. Hence it exploits a vector architecture, but is also suited for parallel implementation and can be executed using Basic Linear Algebra (BLAS) subroutines. Computational results on a CRAY Y-MPE264 supercomputer with a set of large multicommodity network flow problems drawn from a military application are presented and analyzed. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Suggested Citation

  • Mustafa C. Pinar & Stavros A. Zenios, 1992. "Parallel Decomposition of Multicommodity Network Flows Using a Linear-Quadratic Penalty Algorithm," INFORMS Journal on Computing, INFORMS, vol. 4(3), pages 235-249, August.
  • Handle: RePEc:inm:orijoc:v:4:y:1992:i:3:p:235-249
    DOI: 10.1287/ijoc.4.3.235

    Download full text from publisher

    File URL:
    Download Restriction: no


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. Richard D. McBride & John W. Mamer, 2004. "Implementing an LU Factorization for the Embedded Network Simplex Algorithm," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 109-119, May.
    2. Paola Cappanera & Antonio Frangioni, 2003. "Symmetric and Asymmetric Parallelization of a Cost-Decomposition Algorithm for Multicommodity Flow Problems," INFORMS Journal on Computing, INFORMS, vol. 15(4), pages 369-384, November.
    3. J. H. Wu, 1997. "Modified Primal Path-Following Scheme for the Monotone Variational Inequality Problem," Journal of Optimization Theory and Applications, Springer, vol. 95(1), pages 189-208, October.

    More about this item


    networks; programming: transportation;


    Access and download statistics


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:4:y:1992:i:3:p:235-249. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Matthew Walls). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.