IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v40y1993i3p305-324.html
   My bibliography  Save this article

Dual‐ascent methods for large‐scale multicommodity flow problems

Author

Listed:
  • Cynthia Barnhart

Abstract

The capacitated multicommodity network flow problem presents itself in a number of problem contexts including transportation, communication, and production. To solve the large‐scale multicommodity flow problems encountered in these fields, we develop dual‐ascent heuristics and a primal solution generator. The dual‐ascent solutions, in addition to determining lower bounds on the optimal objective function value, provide advanced starting solutions for use with primal‐based solution techniques. The primal solution generator uses the dual‐ascent solution to obtain heuristically primal solutions to the multicommodity flow problems. Computational experiments performed on three test problem sets show that the dual‐ascent and primal heuristic procedures typically determine nearoptimal solutions quickly. In addition, by using the dual‐ascent procedure to obtain advanced starting solutions, run times for optimal multicommodity flow procedures are reduced significantly and greatly improved solutions are obtained by the new primal solution generator. © 1993 John Wiley & Sons, Inc.

Suggested Citation

  • Cynthia Barnhart, 1993. "Dual‐ascent methods for large‐scale multicommodity flow problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(3), pages 305-324, April.
    • Handle: RePEc:wly:navres:v:40:y:1993:i:3:p:305-324
    DOI: 10.1002/1520-6750(199304)40:33.0.CO;2-4
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199304)40:33.0.CO;2-4
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(199304)40:33.0.CO;2-4?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
    ---><---

    References listed on IDEAS

    as
    1. Donald Erlenkotter, 1978. "A Dual-Based Procedure for Uncapacitated Facility Location," Operations Research, INFORMS, vol. 26(6), pages 992-1009, December.
    2. William J. Carolan & James E. Hill & Jeffery L. Kennington & Sandra Niemi & Stephen J. Wichmann, 1990. "An Empirical Evaluation of the KORBX® Algorithms for Military Airlift Applications," Operations Research, INFORMS, vol. 38(2), pages 240-248, April.
    3. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Hongbin Liu & Guopeng Song & Tianyu Liu & Bo Guo, 2022. "Multitask Emergency Logistics Planning under Multimodal Transportation," Mathematics, MDPI, vol. 10(19), pages 1-25, October.
    2. Rina R. Schneur & James B. Orlin, 1998. "A Scaling Algorithm for Multicommodity Flow Problems," Operations Research, INFORMS, vol. 46(2), pages 231-246, April.
    3. Antonio Frangioni, 2005. "About Lagrangian Methods in Integer Optimization," Annals of Operations Research, Springer, vol. 139(1), pages 163-193, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Canovas, Lazaro & Garcia, Sergio & Marin, Alfredo, 2007. "Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique," European Journal of Operational Research, Elsevier, vol. 179(3), pages 990-1007, June.
    2. A. Ruszczynski, 1993. "Regularized Decomposition of Stochastic Programs: Algorithmic Techniques and Numerical Results," Working Papers wp93021, International Institute for Applied Systems Analysis.
    3. Ethem Çanakoğlu & İbrahim Muter & Tevfik Aytekin, 2021. "Integrating Individual and Aggregate Diversity in Top- N Recommendation," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 300-318, January.
    4. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    5. Sankaran, Jayaram K., 1995. "Column generation applied to linear programs in course registration," European Journal of Operational Research, Elsevier, vol. 87(2), pages 328-342, December.
    6. Metrane, Abdelmoutalib & Soumis, François & Elhallaoui, Issmail, 2010. "Column generation decomposition with the degenerate constraints in the subproblem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 37-44, November.
    7. Belanger, Nicolas & Desaulniers, Guy & Soumis, Francois & Desrosiers, Jacques, 2006. "Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1754-1766, December.
    8. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    9. Syam, Siddhartha S. & Côté, Murray J., 2010. "A location-allocation model for service providers with application to not-for-profit health care organizations," Omega, Elsevier, vol. 38(3-4), pages 157-166, June.
    10. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    11. Thomas W. M. Vossen & Dan Zhang, 2015. "Reductions of Approximate Linear Programs for Network Revenue Management," Operations Research, INFORMS, vol. 63(6), pages 1352-1371, December.
    12. Ternoy, Jacques Emmanuel, 1969. "Cooperation and economic efficiency," ISU General Staff Papers 196901010800004786, Iowa State University, Department of Economics.
    13. Ibrahim Muter & Tevfik Aytekin, 2017. "Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 405-421, August.
    14. Canca, David & Barrena, Eva, 2018. "The integrated rolling stock circulation and depot location problem in railway rapid transit systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 115-138.
    15. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    16. Mercedes Esteban-Bravo & Jose M. Vidal-Sanz & Gökhan Yildirim, 2014. "Valuing Customer Portfolios with Endogenous Mass and Direct Marketing Interventions Using a Stochastic Dynamic Programming Decomposition," Marketing Science, INFORMS, vol. 33(5), pages 621-640, September.
    17. Harkness, Joseph & ReVelle, Charles, 2003. "Facility location with increasing production costs," European Journal of Operational Research, Elsevier, vol. 145(1), pages 1-13, February.
    18. Ketabchi, Saeed & Behboodi-Kahoo, Malihe, 2015. "Augmented Lagrangian method within L-shaped method for stochastic linear programs," Applied Mathematics and Computation, Elsevier, vol. 266(C), pages 12-20.
    19. El-Sharafy, M. Zaki & Farag, Hany E.Z., 2017. "Back-feed power restoration using distributed constraint optimization in smart distribution grids clustered into microgrids," Applied Energy, Elsevier, vol. 206(C), pages 1102-1117.
    20. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.

    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:wly:navres:v:40:y:1993:i:3:p:305-324. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.