دانلود رایگان مقاله انگلیسی حل مشکل درخت ارتباطی بهینه - الزویر 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.


بدون دیدگاه