مقاله انگلیسی رایگان در مورد حل مشکل درخت ارتباطی بهینه – الزویر ۲۰۱۹

مقاله انگلیسی رایگان در مورد حل مشکل درخت ارتباطی بهینه – الزویر ۲۰۱۹

 

مشخصات مقاله
ترجمه عنوان مقاله حل مشکل درخت ارتباطی بهینه
عنوان انگلیسی مقاله Solving the optimum communication spanning tree problem
انتشار مقاله سال ۲۰۱۹
تعداد صفحات مقاله انگلیسی ۲۷ صفحه
هزینه دانلود مقاله انگلیسی رایگان میباشد.
پایگاه داده نشریه الزویر
نوع نگارش مقاله
مقاله پژوهشی (Research Article)
مقاله بیس این مقاله بیس نمیباشد
نمایه (index) Scopus – Master Journal List – JCR
نوع مقاله ISI
فرمت مقاله انگلیسی  PDF
ایمپکت فاکتور(IF)
۳٫۶۳۲ در سال ۲۰۱۷
شاخص H_index ۲۱۱ در سال ۲۰۱۹
شاخص SJR ۲٫۴۳۷ در سال ۲۰۱۷
شناسه ISSN ۰۳۷۷-۲۲۱۷
شاخص Quartile (چارک) Q1 در سال ۲۰۱۷
رشته های مرتبط مهندسی کامپیوتر
گرایش های مرتبط الگوریتم ها و محاسبات
نوع ارائه مقاله
ژورنال
مجله مجله اروپایی تحقیق در عملیات – European Journal of Operational Research
دانشگاه  Concordia University and Interuniversity Research Centre on Enterprise Networks – Canada H3G 1M8
کلمات کلیدی شبکه، بهینه سازی شبکه، تجزیه بندرز، درختان اسنپینگ
کلمات کلیدی انگلیسی Networks، Network optimization، Benders decomposition، Spanning trees
شناسه دیجیتال – doi
https://doi.org/10.1016/j.ejor.2018.07.055
کد محصول  E10783
وضعیت ترجمه مقاله  ترجمه آماده این مقاله موجود نمیباشد. میتوانید از طریق دکمه پایین سفارش دهید.
دانلود رایگان مقاله دانلود رایگان مقاله انگلیسی
سفارش ترجمه این مقاله سفارش ترجمه این مقاله

 

فهرست مطالب مقاله:
Abstract

۱- Introduction

۲- Problem definition

۳- Benders decomposition for the OCT

۴- An exact algorithm for the OCT

۵- Computational experiments

۶- 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| − ۱ links. Optimum communication spanning trees offer a balance between low operational costs on networks using a minimum number of links.

ثبت دیدگاه