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

قیمت خرید این محصول

رایگان

دانلود مقاله انگلیسی سفارش ترجمه این مقاله

عنوان فارسی

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

عنوان انگلیسی

Solving the optimum communication spanning tree problem

صفحات مقاله فارسی

0

صفحات مقاله انگلیسی

27

سال انتشار

2019

نشریه

الزویر - Elsevier

فرمت مقاله انگلیسی

PDF

نوع مقاله

ISI

نوع نگارش

مقالات پژوهشی (تحقیقاتی)

رفرنس

دارد

پایگاه

اسکوپوس

کد محصول

E10783

رشته های مرتبط با این مقاله

مهندسی کامپیوتر

گرایش های مرتبط با این مقاله

الگوریتم ها و محاسبات

مجله

مجله اروپایی تحقیق در عملیات - European Journal of Operational Research

دانشگاه

Concordia University and Interuniversity Research Centre on Enterprise Networks - Canada H3G 1M8

کلمات کلیدی

شبکه، بهینه سازی شبکه، تجزیه بندرز، درختان اسنپینگ

doi یا شناسه دیجیتال

https://doi.org/10.1016/j.ejor.2018.07.055

برای سفارش ترجمه این مقاله با کیفیت عالی و در کوتاه ترین زمان ممکن توسط مترجمین مجرب سایت ایران عرضه؛ روی دکمه سبز رنگ کلیک نمایید.

۰.۰ (بدون امتیاز)

امتیاز دهید

چکیده

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.

نتیجه گیری

Conclusion

We have provided an exact algorithm for the OCT that is 100 times faster and is able to solve larger instances than the state-of-the-art. The proposed algorithm uses a strong Benders reformulation for the OCT and exploits problem specific structure to obtain Pareto-optimal Benders cuts efficiently, guarantee feasibility, select branching variables and obtain high quality solutions during the enumeration process. Finally, a new testbed of larger instances has been presented to be used for benchmarking in future research. Our results support the use of a Benders-based branch-and-cut for network design emphasizing on the importance of combining the right algorithmic enhancements. An interesting path for future research would be to strengthen the quality of the lower bounds obtained at the nodes of the enumeration tree by: (i) exploring the use of the combinatorial bounds, evaluating them at some nodes of the enumeration tree while considering the fixed edges to further improve the quality of the bounds, and (ii) using lifting procedures for Benders optimality cuts that use similar logical arguments as the ones used in the combinatorial cuts.

برچسب‌ها: دانلود رایگان مقالات انگلیسی مهندسی کامپیوتر، دانلود رایگان مقالات isi