کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10523831 957099 2005 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation
چکیده انگلیسی
Various techniques for building relaxations and generating valid inequalities for pure or mixed integer programming problems without special structure are reviewed and compared computationally. Besides classical techniques such as Gomory cuts, Mixed Integer Rounding cuts, lift-and-project and reformulation-linearization techniques, a new variant is also investigated: the use of the relaxation corresponding to the intersection of simple disjunction polyhedra (i.e. the so-called elementary closure of lift-and-project cuts). Systematic comparative computational results are reported on series of test problems including multidimensional knapsack problems (MKP) and MIPLIB test problems. From the results obtained, the relaxation based on the elementary closure of lift-and-project cuts appears to be one of the most promising.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 2, Issue 4, December 2005, Pages 288-307
نویسندگان
, ,