A branch-and-cut algorithm for the Multiple Steiner TSP with Order constraints |
| |
| Institution: | 1. University of Wisconsin–Madison, United States;2. School of Mathematics, Jilin University, China;3. Department of Computer Science and Engineering, Shanghai Jiao Tong University, China;1. Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran;2. Department of Industrial Engineering, Amirkabir University of Technology, 424 Hafez Avenue, Tehran, Iran;1. Centro de Automática y Robótica (CAR), UPM-CSIC, C/ Jose Gutiérrez Abascal, 2, 28006 Madrid, Spain;2. Laboratory of Algorithms and Technologies for Networks Analysis, National Research University Higher School of Economics, 136 Rodionova Street, Niznhy Novgorod, Russia |
| |
| Abstract: | The paper deals with a problem motivated by survivability issues in multilayer IP-over-WDM telecommunication networks. Given a set of traffic demands for which we know a survivable routing in the IP layer, our purpose is to look for the corresponding survivable topology in the WDM layer. The problem amounts to Multiple Steiner TSPs with order constraints. We propose an integer linear programming formulation for the problem and investigate the associated polytope. We also present new valid inequalities and discuss their facial aspect. Based on this, we devise a Branch-and-cut algorithm and present preliminary computational results. |
| |
| Keywords: | IP-over-WDM networks Steiner TSP order constraint Branch-and-cut algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
