حل مشکل درخت ارتباطی بهینه
Abstract
1- Introduction
2- Problem definition
3- Benders decomposition for the OCT
4- An exact algorithm for the OCT
5- Computational experiments
6- Conclusion
References
Abstract
This paper presents an algorithm based on Benders decomposition to solve the optimum communication spanning tree problem. The algorithm integrates within a branch-and-cut framework a stronger reformulation of the problem, combinatorial lower bounds, in-tree heuristics, fast separation algorithms, and a tailored branching rule. Computational experiments show solution time savings of up to three orders of magnitude compared to state-of-the-art exact algorithms. In addition, our algorithm is able to prove optimality for five unsolved instances in the literature and four from a new set of larger instances.
Introduction
Network optimization models are able to capture the system-wide interactions of decisions inherent to transportation and communication systems. They have thus become an important tool for designing and managing networks (Ahuja et al., 1993). While the most generic network design problem seeks the ideal trade-off between initial investment and operational costs, there are often other efficiency criteria such as capacity and robustness that need to be considered. Some examples are the design of minimum spanning trees (Kruskal, 1956; Prim, 1957), Hamiltonian cycles (Tutte, 1946), survivable networks (Kerivin and Mahjoub, 2005), and networks with connectivity requirements (Magnanti and Raghavan, 2005). The optimum communication spanning tree problem (OCT) is another such example. Introduced by Hu (1974), the OCT seeks to find a tree spanning all N nodes of an underlying network with minimal operational cost for communicating a set R of node-to-node requests. The use of optimum communication spanning trees arises when communication requests between node pairs are known in advance and the objective is to minimize the communication costs after the network is built. When this is the sole efficiency criterion, the optimal solution is the union of shortest paths between node pairs which, except for particular distance structures, will contain more than |N| − 1 links. Optimum communication spanning trees offer a balance between low operational costs on networks using a minimum number of links.