حل مشکل درخت ارتباطی بهینه
ترجمه نشده

حل مشکل درخت ارتباطی بهینه

عنوان فارسی مقاله: حل مشکل درخت ارتباطی بهینه
عنوان انگلیسی مقاله: Solving the optimum communication spanning tree problem
مجله/کنفرانس: مجله اروپایی تحقیق در عملیات - European Journal of Operational Research
رشته های تحصیلی مرتبط: مهندسی کامپیوتر
گرایش های تحصیلی مرتبط: الگوریتم ها و محاسبات
کلمات کلیدی فارسی: شبکه، بهینه سازی شبکه، تجزیه بندرز، درختان اسنپینگ
کلمات کلیدی انگلیسی: Networks، Network optimization، Benders decomposition، Spanning trees
نوع نگارش مقاله: مقاله پژوهشی (Research Article)
نمایه: Scopus - Master Journal List - JCR
شناسه دیجیتال (DOI): https://doi.org/10.1016/j.ejor.2018.07.055
دانشگاه: Concordia University and Interuniversity Research Centre on Enterprise Networks - Canada H3G 1M8
ناشر: الزویر - Elsevier
نوع ارائه مقاله: ژورنال
نوع مقاله: ISI
سال انتشار مقاله: 2019
ایمپکت فاکتور: 3/632 در سال 2017
شاخص H_index: 211 در سال 2019
شاخص SJR: 2/437 در سال 2017
شناسه ISSN: 0377-2217
شاخص Quartile (چارک): Q1 در سال 2017
فرمت مقاله انگلیسی: PDF
تعداد صفحات مقاله انگلیسی: 27
وضعیت ترجمه: ترجمه نشده است
قیمت مقاله انگلیسی: رایگان
آیا این مقاله بیس است: خیر
کد محصول: E10783
فهرست انگلیسی مطالب

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.

  • اشتراک گذاری در

دیدگاه خود را بنویسید:

تاکنون دیدگاهی برای این نوشته ارسال نشده است

حل مشکل درخت ارتباطی بهینه
نوشته های مرتبط
مقالات جدید
لوگوی رسانه های برخط

logo-samandehi

پیوندها