کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4960055 | 1445965 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new lift-and-project operator
ترجمه فارسی عنوان
یک اپراتور جدید و بلندپرواز
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی عدد صحیح آسانسور و پروژه، فرمول های توسعه یافته، هواپیما برش،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
In this paper, we analyze the strength of split cuts in a lift-and-project framework. We first observe that the Lovász-Schrijver and Sherali-Adams lift-and-project operator hierarchies can be viewed as applying specific 0-1 split cuts to an appropriate extended formulation and demonstrate how to strengthen these hierarchies using additional split cuts. More precisely, we define a new operator that adds all 0-1 split cuts to the extended formulation. For 0-1 mixed-integer sets with k binary variables, this new operator is guaranteed to obtain the integer hull in âk/2â steps compared to k steps for the Lovász-Schrijver or the Sherali-Adams operator. We also present computational results on the stable set problem with our new operator.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 257, Issue 2, 1 March 2017, Pages 420-428
Journal: European Journal of Operational Research - Volume 257, Issue 2, 1 March 2017, Pages 420-428
نویسندگان
Merve Bodur, Sanjeeb Dash, Oktay Günlük,