کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141841 | 957095 | 2008 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes](/preview/png/1141841.png)
چکیده انگلیسی
Cover inequalities are commonly used cutting planes for the 0–1 knapsack problem. This paper describes a linear-time algorithm (assuming the knapsack is sorted) to simultaneously lift a set of variables into a cover inequality. Conditions for this process to result in valid and facet-defining inequalities are presented. In many instances, the resulting simultaneously lifted cover inequality cannot be obtained by sequentially lifting over any cover inequality. Some computational results demonstrate that simultaneously lifted cover inequalities are plentiful, easy to find and can be computationally beneficial.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 5, Issue 2, May 2008, Pages 254–261
Journal: Discrete Optimization - Volume 5, Issue 2, May 2008, Pages 254–261
نویسندگان
Todd Easton, Kevin Hooker,