کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
477716 | 1446179 | 2008 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Local and global lifted cover inequalities for the 0–1 multidimensional knapsack problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The 0–1 multidimensional knapsack problem (0–1 MKP) is a well-known (and strongly NPNP-hard) combinatorial optimization problem with many applications. Up to now, the majority of upper bounding techniques for the 0–1 MKP have been based on Lagrangian or surrogate relaxation. We show that good upper bounds can be obtained by a cutting plane method based on lifted cover inequalities (LCIs). As well as using traditional LCIs, we use some new ‘global’ LCIs, which take the whole constraint matrix into account.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 186, Issue 1, 1 April 2008, Pages 91–103
Journal: European Journal of Operational Research - Volume 186, Issue 1, 1 April 2008, Pages 91–103
نویسندگان
Konstantinos Kaparis, Adam N. Letchford,