Network Migration Problem: A Hybrid Logic-Based Benders Decomposition Approach
针对电信网络升级中的迁移规划问题，首次提出精确求解方法，采用逻辑Benders分解结合约束规划与列生成，在真实网络实例上验证了计算效率。
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. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Funding: This work was supported by Mitacs. SciNet is funded by the Canada Foundation for Innovation, the Government of Ontario, Ontario Research Fund–Research Excellence, and the University of Toronto. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2023.1280 .