IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v68y2017i8d10.1057_s41274-016-0144-9.html
   My bibliography  Save this article

An origin-based model for unique shortest path routing

Author

Listed:
  • Changyong Zhang

    (Curtin University Sarawak)

Abstract

Link weights are the main parameters of shortest path routing protocols, the most commonly used protocols for IP networks. The problem of optimally setting link weights for unique shortest path routing is addressed. Due to the complexity of the constraints involved, there exist challenges to formulate the problem in such a way based on which a more efficient solution algorithm than the existing ones may be developed. In this paper, an exact formulation is first introduced and then mathematically proved correct. It is further illustrated that the formulation has advantages over a prior one in terms of both constraint structure and model size for a proposed decomposition method to solve the problem.

Suggested Citation

  • Changyong Zhang, 2017. "An origin-based model for unique shortest path routing," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 935-951, August.
    • Handle: RePEc:pal:jorsoc:v:68:y:2017:i:8:d:10.1057_s41274-016-0144-9
    DOI: 10.1057/s41274-016-0144-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/s41274-016-0144-9
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/s41274-016-0144-9?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
    ---><---

    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. DINITZ, Yefim & GARG, Naveen & GOEMANS, Michel X., 1999. "On the single-source unsplittable flow problem," LIDAM Reprints CORE 1433, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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 & Bernard Fortz & Mikkel Thorup & Hakan Ümit, 2013. "Intra-domain traffic engineering with shortest path routing protocols," Annals of Operations Research, Springer, vol. 204(1), pages 65-95, April.
    4. Ravindra K. Ahuja & James B. Orlin, 2001. "Inverse Optimization," Operations Research, INFORMS, vol. 49(5), pages 771-783, October.
    5. Kyungchul Park & Seokhoon Kang & Sungsoo Park, 1996. "An Integer Programming Approach to the Bandwidth Packing Problem," Management Science, INFORMS, vol. 42(9), pages 1277-1291, September.
    6. F. Benjamin Zhan & Charles E. Noon, 1998. "Shortest Path Algorithms: An Evaluation Using Real Road Networks," Transportation Science, INFORMS, vol. 32(1), pages 65-73, February.
    7. Luciana S. Buriol & Mauricio G. C. Resende & Mikkel Thorup, 2008. "Speeding Up Dynamic Shortest-Path Algorithms," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 191-204, May.
    8. M. Ericsson & M.G.C. Resende & P.M. Pardalos, 2002. "A Genetic Algorithm for the Weight Setting Problem in OSPF Routing," Journal of Combinatorial Optimization, Springer, vol. 6(3), pages 299-333, September.
    9. Kaj Holmberg & Di Yuan, 2000. "A Lagrangian Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem," Operations Research, INFORMS, vol. 48(3), pages 461-481, June.
    Full references (including those not matched with items on IDEAS)

    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. Ayşegül Altın & Bernard Fortz & Mikkel Thorup & Hakan Ümit, 2013. "Intra-domain traffic engineering with shortest path routing protocols," Annals of Operations Research, Springer, vol. 204(1), pages 65-95, April.
    2. Kang, Jangha & Park, Kyungchul & Park, Sungsoo, 2009. "Optimal multicast route packing," European Journal of Operational Research, Elsevier, vol. 196(1), pages 351-359, July.
    3. Baris Yildiz & Martin Savelsbergh, 2019. "Provably High-Quality Solutions for the Meal Delivery Routing Problem," Transportation Science, INFORMS, vol. 53(5), pages 1372-1388, September.
    4. Seohee Kim & Chungmok Lee, 2021. "A branch and price approach for the robust bandwidth packing problem with queuing delays," Annals of Operations Research, Springer, vol. 307(1), pages 251-275, December.
    5. Jinil Han & Kyungsik Lee & Chungmok Lee & Sungsoo Park, 2013. "Exact Algorithms for a Bandwidth Packing Problem with Queueing Delay Guarantees," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 585-596, August.
    6. Jayaswal, Sachin & Vidyarthi, Navneet & Das, Sagnik, 2014. "An Efficient Solution Approach for Combinatorial Bandwidth Packing Problem with Queuing Delays," IIMA Working Papers WP2014-12-05, Indian Institute of Management Ahmedabad, Research and Publication Department.
    7. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    8. Barış Yıldız & Oya Ekin Karaşan, 2017. "Regenerator Location Problem in Flexible Optical Networks," Operations Research, INFORMS, vol. 65(3), pages 595-620, June.
    9. Fortz, Bernard & Gouveia, Luís & Joyce-Moniz, Martim, 2017. "Models for the piecewise linear unsplittable multicommodity flow problems," European Journal of Operational Research, Elsevier, vol. 261(1), pages 30-42.
    10. Peter Broström & Kaj Holmberg, 2006. "Multiobjective design of survivable IP networks," Annals of Operations Research, Springer, vol. 147(1), pages 235-253, October.
    11. François Lamothe & Emmanuel Rachelson & Alain Haït & Cedric Baudoin & Jean-Baptiste Dupé, 2021. "Randomized rounding algorithms for large scale unsplittable flow problems," Journal of Heuristics, Springer, vol. 27(6), pages 1081-1110, December.
    12. Almobaideen, Wesam & Krayshan, Rand & Allan, Mamoon & Saadeh, Maha, 2017. "Internet of Things: Geographical Routing based on healthcare centers vicinity for mobile smart tourism destination," Technological Forecasting and Social Change, Elsevier, vol. 123(C), pages 342-350.
    13. Anil Aswani & Zuo-Jun Max Shen & Auyon Siddiq, 2019. "Data-Driven Incentive Design in the Medicare Shared Savings Program," Operations Research, INFORMS, vol. 67(4), pages 1002-1026, July.
    14. Vidyarthi, Navneet & Jayaswal, Sachin & Chetty, Vikranth Babu Tirumala, 2013. "Exact Solution to Bandwidth Packing Problem with Queuing Delays," IIMA Working Papers WP2013-11-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    15. 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.
    16. Amy Cohn & Michael Magazine & George Polak, 2009. "Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(3), pages 215-225, April.
    17. Liang Chen & Wei-Kun Chen & Mu-Ming Yang & Yu-Hong Dai, 2021. "An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron," Journal of Global Optimization, Springer, vol. 81(3), pages 659-689, November.
    18. Bernard Gendron & Luis Gouveia, 2017. "Reformulations by Discretization for Piecewise Linear Integer Multicommodity Network Flow Problems," Transportation Science, INFORMS, vol. 51(2), pages 629-649, May.
    19. Ashwin Arulselvan & Mohsen Rezapour, 2017. "Exact Approaches for Designing Multifacility Buy-at-Bulk Networks," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 597-611, November.
    20. Paraskevopoulos, Dimitris C. & Gürel, Sinan & Bektaş, Tolga, 2016. "The congested multicommodity network design problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 166-187.

    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:pal:jorsoc:v:68:y:2017:i:8:d:10.1057_s41274-016-0144-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    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.