کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9663724 | 1446240 | 2005 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Partial convexification cuts for 0-1 mixed-integer programs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Partial convexification cuts for 0-1 mixed-integer programs Partial convexification cuts for 0-1 mixed-integer programs](/preview/png/9663724.png)
چکیده انگلیسی
In this research, we propose a new cut generation scheme based on constructing a partial convex hull representation for a given 0-1 mixed-integer programming problem by using the reformulation-linearization technique (RLT). We derive a separation problem that projects the extended space of the RLT formulation into the original space, in order to generate a cut that deletes a current fractional solution. Naturally, the success of such a partial convexification based cutting plane scheme depends on the process used to tradeoff the strength of the cut derived and the effort expended. Accordingly, we investigate several variable selection rules for performing this convexification, along with restricted versions of the accompanying separation problems, so as to be able to derive strong cuts within a reasonable effort. We also develop a strengthening procedure that enhances the generated cut by considering the binariness of the remaining unselected 0-1 variables. Finally, we present some promising computational results that provide insights into implementing the proposed cutting plane methodology.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 165, Issue 3, 16 September 2005, Pages 625-648
Journal: European Journal of Operational Research - Volume 165, Issue 3, 16 September 2005, Pages 625-648
نویسندگان
Hanif D. Sherali, Youngho Lee, Youngjin Kim,