کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871096 1440178 2018 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
General cut-generating procedures for the stable set polytope
ترجمه فارسی عنوان
روشهای عمومی برش برای مجموعه چند ضلعی پایدار
کلمات کلیدی
برنامه ریزی عدد صحیح چندضلعی، تعریف نسبی، مجموعه های ثابت
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We propose general separation procedures for generating cuts for the stable set polytope, inspired by a procedure by Rossi and Smriglio and applying a lifting method by Xavier and Campêlo. In contrast to existing cut-generating procedures, ours generate both rank and non-rank valid inequalities, hence they are of a more general nature than existing methods. This is accomplished by iteratively solving a lifting problem, which consists of a maximum weighted stable set problem on a smaller graph. Computational experience on DIMACS benchmark instances shows that the proposed approach may be a useful tool for generating cuts for the stable set polytope.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 28-41
نویسندگان
, , , ,