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

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