IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v35y2023i3p593-613.html
   My bibliography  Save this article

Network Migration Problem: A Hybrid Logic-Based Benders Decomposition Approach

Author

Listed:
  • Maryam Daryalal

    (Department of Decision Sciences, HEC Montréal, Montréal, Québec H3T 2A7, Canada)

  • Hamed Pouya

    (Ciena Canada, Inc., Ottawa, Ontario K2K 0L1, Canada)

  • Marc Antoine DeSantis

    (Ciena Canada, Inc., Montréal, Québec H4S 2A9, Canada)

Abstract

Telecommunication networks frequently face technological advancements and need to upgrade their infrastructure. Adapting legacy networks to the latest technology requires synchronized technicians responsible for migrating the equipment. The goal of the network migration problem is to find an optimal plan for this process. This is a defining step in the customer acquisition of telecommunications service suppliers, and its outcome directly impacts the network owners’ purchasing behavior. We propose the first exact method for the network migration problem, a logic-based Benders decomposition approach that benefits from a hybrid constraint programming–based column generation in its master problem and a constraint programming model in its subproblem. This integrated solution technique is applicable to any integer programming problem with similar structure, most notably the vehicle routing problem with node synchronization constraints. Comprehensive evaluation of our method over instances based on six real networks demonstrates the computational efficiency of the algorithm in obtaining quality solutions. We also show the merit of each incorporated optimization paradigm in achieving this performance.

Suggested Citation

  • Maryam Daryalal & Hamed Pouya & Marc Antoine DeSantis, 2023. "Network Migration Problem: A Hybrid Logic-Based Benders Decomposition Approach," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 593-613, May.
    • Handle: RePEc:inm:orijoc:v:35:y:2023:i:3:p:593-613
    DOI: 10.1287/ijoc.2023.1280
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2023.1280
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2023.1280?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. Louis-Martin Rousseau & Michel Gendreau & Gilles Pesant & Filippo Focacci, 2004. "Solving VRPTWs with Constraint Programming Based Column Generation," Annals of Operations Research, Springer, vol. 130(1), pages 199-216, August.
    2. Roshanaei, Vahid & Luong, Curtiss & Aleman, Dionne M. & Urbach, David, 2017. "Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling," European Journal of Operational Research, Elsevier, vol. 257(2), pages 439-455.
    3. Vipul Jain & Ignacio E. Grossmann, 2001. "Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 13(4), pages 258-276, November.
    4. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    5. Gustavo Angulo & Shabbir Ahmed & Santanu S. Dey, 2016. "Improving the Integer L-Shaped Method," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 483-499, August.
    6. Reinhardt, Line Blander & Clausen, Tommy & Pisinger, David, 2013. "Synchronized dial-a-ride transportation of disabled passengers at airports," European Journal of Operational Research, Elsevier, vol. 225(1), pages 106-117.
    7. Babu R. Dawadi & Danda B. Rawat & Shashidhar R. Joshi & Pietro Manzoni & Martina M. Keitsch, 2021. "Migration cost optimization for service provider legacy network migration to software‐defined IPv6 network," International Journal of Network Management, John Wiley & Sons, vol. 31(4), July.
    8. Bredström, David & Rönnqvist, Mikael, 2007. "A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints," Discussion Papers 2007/7, Norwegian School of Economics, Department of Business and Management Science.
    9. Hossein Hashemi Doulabi & Gilles Pesant & Louis-Martin Rousseau, 2020. "Vehicle Routing Problems with Synchronized Visits and Stochastic Travel and Service Times: Applications in Healthcare," Transportation Science, INFORMS, vol. 54(4), pages 1053-1072, July.
    10. John N. Hooker, 2012. "Integrated Methods for Optimization," International Series in Operations Research and Management Science, Springer, number 978-1-4614-1900-6, September.
    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. Mohamed Cissé & Semih Yalçindag & Yannick Kergosien & Evren Sahin & Christophe Lenté & Andrea Matta, 2017. "OR problems related to Home Health Care: A review of relevant routing and scheduling problems," Post-Print hal-01736714, HAL.
    2. Naderi, Bahman & Begen, Mehmet A. & Zaric, Gregory S. & Roshanaei, Vahid, 2023. "A novel and efficient exact technique for integrated staffing, assignment, routing, and scheduling of home care services under uncertainty," Omega, Elsevier, vol. 116(C).
    3. Qin, Tianbao & Du, Yuquan & Sha, Mei, 2016. "Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 87(C), pages 167-185.
    4. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    5. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    6. Sophie N. Parragh & Karl F. Doerner, 2018. "Solving routing problems with pairwise synchronization constraints," 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. 26(2), pages 443-464, June.
    7. Guo, Penghui & Zhu, Jianjun, 2023. "Capacity reservation for humanitarian relief: A logic-based Benders decomposition method with subgradient cut," European Journal of Operational Research, Elsevier, vol. 311(3), pages 942-970.
    8. Drexl, Michael, 2013. "Applications of the vehicle routing problem with trailers and transshipments," European Journal of Operational Research, Elsevier, vol. 227(2), pages 275-283.
    9. Johnsen, Lennart C. & Meisel, Frank, 2022. "Interrelated trips in the rural dial-a-ride problem with autonomous vehicles," European Journal of Operational Research, Elsevier, vol. 303(1), pages 201-219.
    10. Gohram Baloch & Fatma Gzara, 2020. "Strategic Network Design for Parcel Delivery with Drones Under Competition," Transportation Science, INFORMS, vol. 54(1), pages 204-228, January.
    11. Bahman Naderi & Vahid Roshanaei & Mehmet A. Begen & Dionne M. Aleman & David R. Urbach, 2021. "Increased Surgical Capacity without Additional Resources: Generalized Operating Room Planning and Scheduling," Production and Operations Management, Production and Operations Management Society, vol. 30(8), pages 2608-2635, August.
    12. Özgün Elçi & John Hooker, 2022. "Stochastic Planning and Scheduling with Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2428-2442, September.
    13. Niels Agatz & Paul Bouman & Marie Schmidt, 2018. "Optimization Approaches for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 52(4), pages 965-981, August.
    14. Kevin Ryan & Shabbir Ahmed & Santanu S. Dey & Deepak Rajan & Amelia Musselman & Jean-Paul Watson, 2020. "Optimization-Driven Scenario Grouping," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 805-821, July.
    15. John N. Hooker, 2002. "Logic, Optimization, and Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 295-321, November.
    16. Amine Lamine & Mahdi Khemakhem & Brahim Hnich & Habib Chabchoub, 2016. "Solving constrained optimization problems by solution-based decomposition search," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 672-695, October.
    17. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    18. Yanchao Liu, 2019. "A Progressive Motion-Planning Algorithm and Traffic Flow Analysis for High-Density 2D Traffic," Transportation Science, INFORMS, vol. 53(6), pages 1501-1525, November.
    19. Nuraiman, Dian & Ozlen, Melih & Hearne, John, 2020. "A spatial decomposition based math-heuristic approach to the asset protection problem," Operations Research Perspectives, Elsevier, vol. 7(C).
    20. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.

    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:orijoc:v:35:y:2023:i:3:p:593-613. 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: Chris Asher (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. RePEc uses bibliographic data supplied by the respective publishers.