کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
483220 | 1446201 | 2007 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new lower bound for the linear knapsack problem with general integer variables
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
It is well known that the linear knapsack problem with general integer variables (LKP) is NP-hard. In this paper we first introduce a special case of this problem and develop an O(n) algorithm to solve it. We then show how this algorithm can be used efficiently to obtain a lower bound for a general instance of LKP and prove that it is at least as good as the linear programming lower bound. We also present the results of a computational study that show that for certain classes of problems the proposed bound on average is tighter than other bounds proposed in the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 178, Issue 3, 1 May 2007, Pages 738–754
Journal: European Journal of Operational Research - Volume 178, Issue 3, 1 May 2007, Pages 738–754
نویسندگان
Kamlesh Mathur, Prahalad Venkateshan,