IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v23y1977i9p994-1004.html
   My bibliography  Save this article

An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems

Author

Listed:
  • Jeff Kennington

    (Southern Methodist University)

  • Mohamed Shalaby

    (Southern Methodist University)

Abstract

This paper presents a heuristic technique for obtaining good solutions to large multicommodity network flow problems. The general approach is to allocate the arc capacities among the individual commodities and hence decompose the problem into a set of one-commodity problems. The one-commodity problems are solved and the combined solution is compared to a lower bound. If the solution is within an acceptable deviation from the lower bound, the procedure terminates. Otherwise, the arc capacities are reallocated and the subprograms are resolved. The reallocation is based on a subgradient optimization approach. Hence, the heuristic technique involves no matrix operations which may lead to round-off errors, the storage requirements are modest, and almost all operations are carried out directly on one-commodity networks. The technique has been coded and the initial computational experience is encouraging.

Suggested Citation

  • Jeff Kennington & Mohamed Shalaby, 1977. "An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems," Management Science, INFORMS, vol. 23(9), pages 994-1004, May.
    • Handle: RePEc:inm:ormnsc:v:23:y:1977:i:9:p:994-1004
    DOI: 10.1287/mnsc.23.9.994
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.23.9.994
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.23.9.994?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

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


    Cited by:

    1. Kraft, Edwin R., 2002. "Scheduling railway freight delivery appointments using a bid price approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(2), pages 145-165, February.
    2. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    3. N. Maculan & C.P. Santiago & E.M. Macambira & M.H.C. Jardim, 2003. "An O(n) Algorithm for Projecting a Vector on the Intersection of a Hyperplane and a Box in Rn," Journal of Optimization Theory and Applications, Springer, vol. 117(3), pages 553-574, June.
    4. Kaj Holmberg & Di Yuan, 2003. "A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 42-57, February.
    5. Larsson, Torbjörn & Patriksson, Michael, 1995. "An augmented lagrangean dual algorithm for link capacity side constrained traffic assignment problems," Transportation Research Part B: Methodological, Elsevier, vol. 29(6), pages 433-455, December.
    6. Frangioni, Antonio & Gorgone, Enrico, 2013. "A library for continuous convex separable quadratic knapsack problems," European Journal of Operational Research, Elsevier, vol. 229(1), pages 37-40.
    7. Hong T. M. Chu & Ling Liang & Kim-Chuan Toh & Lei Yang, 2023. "An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems," Computational Optimization and Applications, Springer, vol. 85(1), pages 107-146, May.
    8. Khodakaram Salimifard & Sara Bigharaz, 2022. "The multicommodity network flow problem: state of the art classification, applications, and solution methods," Operational Research, Springer, vol. 22(1), pages 1-47, March.
    9. Larsson, Torbjorn & Patriksson, Michael & Stromberg, Ann-Brith, 1996. "Conditional subgradient optimization -- Theory and applications," European Journal of Operational Research, Elsevier, vol. 88(2), pages 382-403, January.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    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:ormnsc:v:23:y:1977:i:9:p:994-1004. See general information about how to correct material in RePEc.

    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 bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.