کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903380 | 1632567 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A Branch-and-Bound Algorithm for the Minimum Cost Bipartite Perfect Matching Problem with Conflict Pair Constraints
ترجمه فارسی عنوان
یک الگوریتم شعبه و یکپارچه برای کمترین هزینه همبستگی دو طرفه با محدودیت های همبستگی متقابل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شاخه و مرز، مشکل تطبیق کامل دو طرفه، نمودار تعارض، مشکل تکلیف
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
In this study we consider the Minimum Cost Bipartite Perfect Matching Problem with Conflict Pair Constraints (MCBPMPC) on bipartite graphs. Given a bipartite graph G with a cost associated with each edge and a conflict set of edge pairs, the MCBPMPC consists of finding a perfect matching with the lowest total cost such that no more than one edge is selected from each pair in the conflict set. A specially tailored branch-and-bound (B&B) algorithm is introduced. Computational experiments are performed on randomly generated instances. According to the extensive experiments, the suggested B&B algorithm yields promising results compared to a state-of-the-art mixed integer linear programming solver.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 64, February 2018, Pages 5-14
Journal: Electronic Notes in Discrete Mathematics - Volume 64, February 2018, Pages 5-14
نویسندگان
Temel Ãncan, Ä°. Kuban Altınel,