کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142602 | 957157 | 2010 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of cutting-plane proofs using split cuts
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We prove a monotone interpolation property for split cuts which, together with results from Pudlák (1997) [20], implies that cutting-plane proofs which use split cuts (or, equivalently, mixed-integer rounding cuts or Gomory mixed-integer cuts) have exponential length in the worst case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 38, Issue 2, March 2010, Pages 109–114
Journal: Operations Research Letters - Volume 38, Issue 2, March 2010, Pages 109–114
نویسندگان
Sanjeeb Dash,