کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6892696 | 1445456 | 2018 | 29 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An exact algorithm for the Partition Coloring Problem
ترجمه فارسی عنوان
یک الگوریتم دقیق برای مشکل رنگ آمیزی پارتیشن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی ورتکس، پارتیشن بندی رنگ آمیزی، رنگ آمیزی انتخابی نسل ستون، الگوریتم شعبه و قیمت،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We study the Partition Coloring Problem (PCP), a generalization of the Vertex Coloring Problem where the vertex set is partitioned. The PCP asks to select one vertex for each subset of the partition in such a way that the chromatic number of the induced graph is minimum. We propose a new Integer Linear Programming formulation with an exponential number of variables. To solve this formulation to optimality, we design an effective Branch-and-Price algorithm. Good quality initial solutions are computed via a new metaheuristic algorithm based on adaptive large neighborhood search. Extensive computational experiments on a benchmark test of instances from the literature show that our Branch-and-Price algorithm, combined with the new metaheuristic algorithm, is able to solve for the first time to proven optimality several open instances, and compares favorably with the current state-of-the-art exact algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 92, April 2018, Pages 170-181
Journal: Computers & Operations Research - Volume 92, April 2018, Pages 170-181
نویسندگان
Fabio Furini, Enrico Malaguti, Alberto Santini,