کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
476546 1445998 2015 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimality cuts and a branch-and-cut algorithm for the K-rooted mini-max spanning forest problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Optimality cuts and a branch-and-cut algorithm for the K-rooted mini-max spanning forest problem
چکیده انگلیسی


• We introduce optimality cuts for the K-rooted mini-max spanning forest problem.
• Optimality cuts are used within a new branch-and-cut algorithm.
• Extensive computational testings with the new method are carried out.
• With such an algorithm we are able to substantially improve previous results on the problem.

Let G = (V, E) be an undirected graph with costs associated with its edges and K pre-specified root vertices. The K−rooted mini-max spanning forest problem asks for a spanning forest of G defined by exactly K mutually disjoint trees. Each tree must contain a different root vertex and the cost of the most expensive tree must be minimum. This paper introduces a Branch-and-cut algorithm for the problem. It involves a multi-start Linear Programming heuristic and the separation of some new optimality cuts. Extensive computational tests indicate that the new algorithm significantly improves on the results available in the literature. Improvements being reflected by lower CPU times, smaller enumeration trees, and optimality certificates for previously unattainable K = 2 instances with as many as 200 vertices. Furthermore, for the first time, instances of the problem with K ∈ {3, 4} are solved to proven optimality.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 246, Issue 2, 16 October 2015, Pages 392–399
نویسندگان
, , ,