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

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
نویسندگان
,