IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v200y2010i1p1-8.html
   My bibliography  Save this article

A global optimization algorithm for reliable network design

Author

Listed:
  • Desai, Jitamitra
  • Sen, Suvrajeet

Abstract

In this paper, we consider the problem of designing reliable networks that satisfy supply/demand, flow balance, and capacity constraints, while simultaneously allocating certain resources to mitigate the arc failure probabilities in such a manner as to minimize the total cost of network design and resource allocation. The resulting model formulation is a nonconvex mixed-integer 0-1 program, for which a tight linear programming relaxation is derived using RLT-based variable substitution strategies and a polyhedral outer-approximation technique. This LP relaxation is subsequently embedded within a specialized branch-and-bound procedure, and the proposed approach is proven to converge to a global optimum. Various alternative partitioning strategies that could potentially be employed in the context of this branch-and-bound framework, while preserving the theoretical convergence property, are also explored. Computational results are reported for a hypothetical scenario based on different parameter inputs and alternative branching strategies. Related optimization models that conform to the same class of problems are also briefly presented.

Suggested Citation

  • Desai, Jitamitra & Sen, Suvrajeet, 2010. "A global optimization algorithm for reliable network design," European Journal of Operational Research, Elsevier, vol. 200(1), pages 1-8, January.
    • Handle: RePEc:eee:ejores:v:200:y:2010:i:1:p:1-8
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)01048-5
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Anantaram Balakrishnan & Thomas L. Magnanti & Prakash Mirchandani, 1994. "A Dual-Based Algorithm for Multi-Level Network Design," Management Science, INFORMS, vol. 40(5), pages 567-581, May.
    2. Gen, Mitsuo & Kumar, Anup & Ryul Kim, Jong, 2005. "Recent network design techniques using evolutionary algorithms," International Journal of Production Economics, Elsevier, vol. 98(2), pages 251-261, November.
    3. Anantaram Balakrishnan & Thomas L. Magnanti & Prakash Mirchandani, 1998. "Designing Hierarchical Survivable Networks," Operations Research, INFORMS, vol. 46(1), pages 116-136, February.
    4. April K. Andreas & J. Cole Smith, 2008. "Mathematical Programming Algorithms for Two-Path Routing Problems with Reliability Considerations," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 553-564, November.
    5. Jianmin Jia & James S. Dyer, 1996. "A Standard Measure of Risk and Risk-Value Models," Management Science, INFORMS, vol. 42(12), pages 1691-1705, December.
    6. Sridhar, Varadharajan & Park, June S., 2000. "Benders-and-cut algorithm for fixed-charge capacitated network design problem," European Journal of Operational Research, Elsevier, vol. 125(3), pages 622-632, September.
    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. Akgün, Ibrahim & Tansel, Barbaros Ç. & Kevin Wood, R., 2011. "The multi-terminal maximum-flow network-interdiction problem," European Journal of Operational Research, Elsevier, vol. 211(2), pages 241-251, June.
    2. Fateme Fotuhi & Nathan Huynh, 2017. "Reliable Intermodal Freight Network Expansion with Demand Uncertainties and Network Disruptions," Networks and Spatial Economics, Springer, vol. 17(2), pages 405-433, June.
    3. Hua Wang & Xiaoning Zhang, 2017. "Game theoretical transportation network design among multiple regions," Annals of Operations Research, Springer, vol. 249(1), pages 97-117, February.
    4. Y. G. Melese & P. W. Heijnen & R. M. Stikkelman & P. M. Herder, 2017. "An Approach for Integrating Valuable Flexibility During Conceptual Design of Networks," Networks and Spatial Economics, Springer, vol. 17(2), pages 317-341, June.
    5. Yan, Xihong & Ren, Xiaorong & Nie, Xiaofeng, 2022. "A budget allocation model for domestic airport network protection," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).

    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. Souza, Fernanda S.H. & Gendreau, Michel & Mateus, Geraldo R., 2014. "Branch-and-price algorithm for the Resilient Multi-level Hop-constrained Network Design," European Journal of Operational Research, Elsevier, vol. 233(1), pages 84-93.
    2. Chardy, M. & Costa, M.-C. & Faye, A. & Trampont, M., 2012. "Optimizing splitter and fiber location in a multilevel optical FTTH network," European Journal of Operational Research, Elsevier, vol. 222(3), pages 430-440.
    3. Agarwal, Y.K. & Aneja, Y.P. & Jayaswal, Sachin, 2022. "Directed fixed charge multicommodity network design: A cutting plane approach using polar duality," European Journal of Operational Research, Elsevier, vol. 299(1), pages 118-136.
    4. Brogan, Anita J. & Stidham Jr., Shaler, 2008. "Non-separation in the mean-lower-partial-moment portfolio optimization problem," European Journal of Operational Research, Elsevier, vol. 184(2), pages 701-710, January.
    5. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    6. Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
    7. He, Ying & Dyer, James S. & Butler, John C. & Jia, Jianmin, 2019. "An additive model of decision making under risk and ambiguity," Journal of Mathematical Economics, Elsevier, vol. 85(C), pages 78-92.
    8. Yang, Jiping & Qiu, Wanhua, 2005. "A measure of risk and a decision-making model based on expected utility and entropy," European Journal of Operational Research, Elsevier, vol. 164(3), pages 792-799, August.
    9. Pablo Cortes & Jesus Muñuzuri & Luis Onieva & Juan Larrañeta & Juan M. Vozmediano & Jose C. Alarcon, 2006. "Andalucía Assesses the Investment Needed to Deploy a Fiber-Optic Network," Interfaces, INFORMS, vol. 36(2), pages 105-117, April.
    10. Thapalia, Biju K. & Crainic, Teodor Gabriel & Kaut, Michal & Wallace, Stein W., 2012. "Single-commodity network design with random edge capacities," European Journal of Operational Research, Elsevier, vol. 220(2), pages 394-403.
    11. Yitong Wang & Tianjun Feng & L. Keller, 2013. "A further exploration of the uncertainty effect," Journal of Risk and Uncertainty, Springer, vol. 47(3), pages 291-310, December.
    12. Masashi Miyagawa, 2009. "Optimal hierarchical system of a grid road network," Annals of Operations Research, Springer, vol. 172(1), pages 349-361, November.
    13. Oya Ekin Karaşan & A. Ridha Mahjoub & Onur Özkök & Hande Yaman, 2014. "Survivability in Hierarchical Telecommunications Networks Under Dual Homing," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 1-15, February.
    14. Albrecht, Peter, 2003. "Risk measures," Papers 03-01, Sonderforschungsbreich 504.
    15. Fausto Errico & Teodor Gabriel Crainic & Federico Malucelli & Maddalena Nonato, 2017. "A Benders Decomposition Approach for the Symmetric TSP with Generalized Latency Arising in the Design of Semiflexible Transit Systems," Transportation Science, INFORMS, vol. 51(2), pages 706-722, May.
    16. Garg, Manish & Smith, J. Cole, 2008. "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios," Omega, Elsevier, vol. 36(6), pages 1057-1071, December.
    17. E A Cabral & E Erkut & G Laporte & R A Patterson, 2008. "Wide area telecommunication network design: application to the Alberta SuperNet," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(11), pages 1460-1470, November.
    18. Janne Gustafsson & Ahti Salo, 2005. "Contingent Portfolio Programming for the Management of Risky Projects," Operations Research, INFORMS, vol. 53(6), pages 946-956, December.
    19. Valeri Zakamouline, 2014. "Portfolio performance evaluation with loss aversion," Quantitative Finance, Taylor & Francis Journals, vol. 14(4), pages 699-710, April.
    20. Preethi Issac & Ann Melissa Campbell, 2017. "Shortest path problem with arc failure scenarios," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 139-163, June.

    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:eee:ejores:v:200:y:2010:i:1:p:1-8. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.