IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v295y2020i1d10.1007_s10479-020-03721-6.html
   My bibliography  Save this article

A new branch-and-cut approach for the generalized regenerator location problem

Author

Listed:
  • Xiangyong Li

    (Tongji University)

  • Y. P. Aneja

    (University of Windsor)

Abstract

In optical networks, a signal can only travel a maximum distance (called optical reach) before its quality deteriorates, needing regenerations by installing regenerators at network nodes. Such an optical reach is an important property of a transmission system, which is a necessary ingredient for enabling optical bypass and thus significantly affects optical network design. In this paper, we study the generalized regenerator location problem (GRLP) where we are given a set S of candidate locations for regenerator placement and a set T of network nodes required to communicate with each other. The GRLP is to find a minimal number of network nodes for regenerator placement, such that for each node pair in T, there exists a path of which no subpath without internal regenerators has a length greater than the given optical reach. Starting with an existing set covering formulation of the problem, we first study the facial structure of the associated polytope. Making use of these polyhedral results, we then present a new branch-and-cut solution approach to solve the GRLP to optimality. With benchmark instances and newly generated instances, we finally evaluate our approach and compare it with an existing method. Computational results demonstrate efficacy of our approach.

Suggested Citation

  • Xiangyong Li & Y. P. Aneja, 2020. "A new branch-and-cut approach for the generalized regenerator location problem," Annals of Operations Research, Springer, vol. 295(1), pages 229-255, December.
    • Handle: RePEc:spr:annopr:v:295:y:2020:i:1:d:10.1007_s10479-020-03721-6
    DOI: 10.1007/s10479-020-03721-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-020-03721-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-020-03721-6?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. Si Chen & Ivana Ljubić & S. Raghavan, 2015. "The Generalized Regenerator Location Problem," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 204-220, May.
    2. Fabio Colombo & Marco Trubian, 2014. "A column generation approach for Multicast Routing and Wavelength Assignment with Delay Constraints in heterogeneous WDM networks," Annals of Operations Research, Springer, vol. 222(1), pages 239-260, November.
    3. Bernard Gendron & Abilio Lucena & Alexandre Salles da Cunha & Luidi Simonetti, 2014. "Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 645-657, November.
    4. Sylvie Borne & Eric Gourdin & Bernard Liau & A. Mahjoub, 2006. "Design of survivable IP-over-optical networks," Annals of Operations Research, Springer, vol. 146(1), pages 41-73, September.
    5. Dorit S. Hochbaum, 2008. "The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem," Operations Research, INFORMS, vol. 56(4), pages 992-1009, August.
    6. Li, Xiangyong & Aneja, Y.P., 2017. "Regenerator location problem: Polyhedral study and effective branch-and-cut algorithms," European Journal of Operational Research, Elsevier, vol. 257(1), pages 25-40.
    7. Austin Buchanan & Je Sang Sung & Sergiy Butenko & Eduardo L. Pasiliao, 2015. "An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 178-188, 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. Zhe Liu & Shurong Li, 2022. "A numerical method for interval multi-objective mixed-integer optimal control problems based on quantum heuristic algorithm," Annals of Operations Research, Springer, vol. 311(2), pages 853-898, April.

    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. Hamidreza Validi & Austin Buchanan, 2020. "The Optimal Design of Low-Latency Virtual Backbones," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 952-967, October.
    2. Li, Xiangyong & Aneja, Y.P., 2017. "Regenerator location problem: Polyhedral study and effective branch-and-cut algorithms," European Journal of Operational Research, Elsevier, vol. 257(1), pages 25-40.
    3. Xinyun Wu & Zhipeng Lü & Fred Glover, 2022. "A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 817-833, March.
    4. Markus Leitner & Ivana Ljubić & Martin Riedler & Mario Ruthmair, 2019. "Exact Approaches for Network Design Problems with Relays," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 171-192, February.
    5. do Forte, Vinicius L. & Hanafi, Saïd & Lucena, Abilio, 2023. "Extended formulations for perfect domination problems and their algorithmic implications," European Journal of Operational Research, Elsevier, vol. 310(2), pages 566-581.
    6. Jiao Zhou & Zhao Zhang & Shaojie Tang & Xiaohui Huang & Ding-Zhu Du, 2018. "Breaking the O (ln n ) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 225-235, May.
    7. Sara Mattia, 2012. "Solving survivable two-layer network design problems by metric inequalities," Computational Optimization and Applications, Springer, vol. 51(2), pages 809-834, March.
    8. Amina Lamghari & Roussos Dimitrakopoulos & Jacques Ferland, 2015. "A hybrid method based on linear programming and variable neighborhood descent for scheduling production in open-pit mines," Journal of Global Optimization, Springer, vol. 63(3), pages 555-582, November.
    9. Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
    10. Lamas, Patricio & Goycoolea, Marcos & Pagnoncelli, Bernardo & Newman, Alexandra, 2024. "A target-time-windows technique for project scheduling under uncertainty," European Journal of Operational Research, Elsevier, vol. 314(2), pages 792-806.
    11. Armin Fügenschuh & Marzena Fügenschuh, 2008. "Integer linear programming models for topology optimization in sheet metal design," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 68(2), pages 313-331, October.
    12. Luís Gouveia & Pedro Patrício & Amaro Sousa, 2008. "Hop-Constrained Node Survivable Network Design: An Application to MPLS over WDM," Networks and Spatial Economics, Springer, vol. 8(1), pages 3-21, March.
    13. Renaud Chicoisne & Daniel Espinoza & Marcos Goycoolea & Eduardo Moreno & Enrique Rubio, 2012. "A New Algorithm for the Open-Pit Mine Production Scheduling Problem," Operations Research, INFORMS, vol. 60(3), pages 517-528, June.
    14. Nancel-Penard, Pierre & Morales, Nelson & Cornillier, Fabien, 2022. "A recursive time aggregation-disaggregation heuristic for the multidimensional and multiperiod precedence-constrained knapsack problem: An application to the open-pit mine block sequencing problem," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1088-1099.
    15. Yiyong Xiao & Abdullah Konak, 2017. "A variable neighborhood search for the network design problem with relays," Journal of Heuristics, Springer, vol. 23(2), pages 137-164, June.
    16. Jélvez, Enrique & Morales, Nelson & Nancel-Penard, Pierre & Cornillier, Fabien, 2020. "A new hybrid heuristic algorithm for the Precedence Constrained Production Scheduling Problem: A mining application," Omega, Elsevier, vol. 94(C).
    17. Gonzalo Muñoz & Daniel Espinoza & Marcos Goycoolea & Eduardo Moreno & Maurice Queyranne & Orlando Rivera Letelier, 2018. "A study of the Bienstock–Zuckerberg algorithm: applications in mining and resource constrained project scheduling," Computational Optimization and Applications, Springer, vol. 69(2), pages 501-534, March.
    18. Whittle, D. & Brazil, M. & Grossman, P.A. & Rubinstein, J.H. & Thomas, D.A., 2018. "Combined optimisation of an open-pit mine outline and the transition depth to underground mining," European Journal of Operational Research, Elsevier, vol. 268(2), pages 624-634.
    19. Madziwa, Lawrence & Pillalamarry, Mallikarjun & Chatterjee, Snehamoy, 2023. "Integrating stochastic mine planning model with ARDL commodity price forecasting," Resources Policy, Elsevier, vol. 85(PB).
    20. Raka Jovanovic & Tatsushi Nishi & Stefan Voß, 2017. "A heuristic approach for dividing graphs into bi-connected components with a size constraint," Journal of Heuristics, Springer, vol. 23(2), pages 111-136, 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:spr:annopr:v:295:y:2020:i:1:d:10.1007_s10479-020-03721-6. 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.springer.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.