IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v60y2012i3p604-610.html
   My bibliography  Save this article

Technical Note---Branch-and-Price-and-Cut Approach to the Robust Network Design Problem Without Flow Bifurcations

Author

Listed:
  • Chungmok Lee

    (IT Convergence Technology Research Laboratory, Electronics and Telecommunications Research Institute, Yuseong-gu, Daejeon 305-700, Republic of Korea, Department of Industrial and Systems Engineering, KAIST, Guseong-dong, Yuseong-gu, Daejeon 305-701, Republic of Korea)

  • Kyungsik Lee

    (Department of Industrial and Management Engineering, Hankuk University of Foreign Studies, Mohyeon-myon, Yongin-si, Gyeonggi-do 449-791, Republic of Korea)

  • Kyungchul Park

    (College of Business Administration, Myongji University, Namgaja-dong, Seodaemun-gu, Seoul 120-728, Republic of Korea)

  • Sungsoo Park

    (Department of Industrial and Systems Engineering, KAIST, Guseong-dong, Yuseong-gu, Daejeon 305-701, Republic of Korea)

Abstract

This paper presents a robust optimization approach to the network design problem under traffic demand uncertainty. We consider the specific case of the network design problem in which there are several alternatives in edge capacity installations and the traffic cannot be split over several paths. A new decomposition approach is proposed that yields a strong LP relaxation and enables traffic demand uncertainty to be addressed efficiently through localization of the uncertainty to each edge of the underlying network. A branch-and-price-and-cut algorithm is subsequently developed and tested on a set of benchmark instances.

Suggested Citation

  • Chungmok Lee & Kyungsik Lee & Kyungchul Park & Sungsoo Park, 2012. "Technical Note---Branch-and-Price-and-Cut Approach to the Robust Network Design Problem Without Flow Bifurcations," Operations Research, INFORMS, vol. 60(3), pages 604-610, June.
  • Handle: RePEc:inm:oropre:v:60:y:2012:i:3:p:604-610
    DOI: 10.1287/opre.1120.1049
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1120.1049
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.1120.1049?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. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    2. Cynthia Barnhart & Christopher A. Hane & Pamela H. Vance, 2000. "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems," Operations Research, INFORMS, vol. 48(2), pages 318-326, April.
    3. Ayşegül Altın & Hande Yaman & Mustafa Ç. Pınar, 2011. "The Robust Network Loading Problem Under Hose Demand Uncertainty: Formulation, Polyhedral Analysis, and Computations," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 75-89, February.
    4. S Mudchanatongsuk & F Ordóñez & J Liu, 2008. "Robust solutions for network design under transportation cost and demand uncertainty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 652-662, May.
    5. Sara Mattia, 2010. "The Robust Network Loading Problem with Dynamic Routing," DIS Technical Reports 2010-03, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    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. Artur Alves Pessoa & Michael Poss, 2015. "Robust Network Design with Uncertain Outsourcing Cost," INFORMS Journal on Computing, INFORMS, vol. 27(3), pages 507-524, August.
    2. Chassein, André & Goerigk, Marc & Kurtz, Jannis & Poss, Michael, 2019. "Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty," European Journal of Operational Research, Elsevier, vol. 279(2), pages 308-319.
    3. Annette M. C. Ficker & Frits C. R. Spieksma & Gerhard J. Woeginger, 2018. "Robust balanced optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(3), pages 239-266, September.

    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. Sara Mattia & Michael Poss, 2018. "A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation," Computational Optimization and Applications, Springer, vol. 69(3), pages 753-800, April.
    2. Hassan Hijazi & Pierre Bonami & Adam Ouorou, 2013. "Robust delay-constrained routing in telecommunications," Annals of Operations Research, Springer, vol. 206(1), pages 163-181, July.
    3. Siqian Shen & Mingdi You & Yintai Ma, 2017. "Single‐commodity stochastic network design under demand and topological uncertainties with insufficient data," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(2), pages 154-173, March.
    4. Artur Alves Pessoa & Michael Poss, 2015. "Robust Network Design with Uncertain Outsourcing Cost," INFORMS Journal on Computing, INFORMS, vol. 27(3), pages 507-524, August.
    5. Roos, Ernst & den Hertog, Dick, 2019. "Reducing conservatism in robust optimization," Other publications TiSEM ad0238cd-de7a-4366-b487-b, Tilburg University, School of Economics and Management.
    6. Ouhimmou, Mustapha & Nourelfath, Mustapha & Bouchard, Mathieu & Bricha, Naji, 2019. "Design of robust distribution network under demand uncertainty: A case study in the pulp and paper," International Journal of Production Economics, Elsevier, vol. 218(C), pages 96-105.
    7. Shahparvari, Shahrooz & Abbasi, Babak, 2017. "Robust stochastic vehicle routing and scheduling for bushfire emergency evacuation: An Australian case study," Transportation Research Part A: Policy and Practice, Elsevier, vol. 104(C), pages 32-49.
    8. Ayşegül Altın & Hande Yaman & Mustafa Ç. Pınar, 2011. "The Robust Network Loading Problem Under Hose Demand Uncertainty: Formulation, Polyhedral Analysis, and Computations," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 75-89, February.
    9. Matthews, Logan R. & Gounaris, Chrysanthos E. & Kevrekidis, Ioannis G., 2019. "Designing networks with resiliency to edge failures using two-stage robust optimization," European Journal of Operational Research, Elsevier, vol. 279(3), pages 704-720.
    10. Ernst Roos & Dick den Hertog, 2020. "Reducing Conservatism in Robust Optimization," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1109-1127, October.
    11. Jianwen Ren & Yingqiang Xu & Shiyuan Wang, 2018. "A Distributed Robust Dispatch Approach for Interconnected Systems with a High Proportion of Wind Power Penetration," Energies, MDPI, Open Access Journal, vol. 11(4), pages 1-18, April.
    12. Shipra Agrawal & Yichuan Ding & Amin Saberi & Yinyu Ye, 2012. "Price of Correlations in Stochastic Optimization," Operations Research, INFORMS, vol. 60(1), pages 150-162, February.
    13. Zhi Chen & Melvyn Sim & Huan Xu, 2019. "Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," Operations Research, INFORMS, vol. 67(5), pages 1328-1344, September.
    14. Stefan Mišković, 2017. "A VNS-LP algorithm for the robust dynamic maximal covering location problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(4), pages 1011-1033, October.
    15. Heydari, Mohammadhossein & Sullivan, Kelly M., 2019. "Robust allocation of testing resources in reliability growth," Reliability Engineering and System Safety, Elsevier, vol. 192(C).
    16. Dimitrios Letsios & Jeremy T. Bradley & Suraj G & Ruth Misener & Natasha Page, 2021. "Approximate and robust bounded job start scheduling for Royal Mail delivery offices," Journal of Scheduling, Springer, vol. 24(2), pages 237-258, April.
    17. Sarhadi, Hassan & Naoum-Sawaya, Joe & Verma, Manish, 2020. "A robust optimization approach to locating and stockpiling marine oil-spill response facilities," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    18. Li, Shukai & Liu, Ronghui & Yang, Lixing & Gao, Ziyou, 2019. "Robust dynamic bus controls considering delay disturbances and passenger demand uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 88-109.
    19. Chassein, André & Dokka, Trivikram & Goerigk, Marc, 2019. "Algorithms and uncertainty sets for data-driven robust shortest path problems," European Journal of Operational Research, Elsevier, vol. 274(2), pages 671-686.
    20. Güray Kara & Ayşe Özmen & Gerhard-Wilhelm Weber, 2019. "Stability advances in robust portfolio optimization under parallelepiped uncertainty," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(1), pages 241-261, March.

    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:oropre:v:60:y:2012:i:3:p:604-610. 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: . General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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: Matthew Walls (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 hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.