A new lower bound for the linear knapsack problem with general integer variables

A new lower bound for the linear knapsack problem with general integer variables

0.00 Avg rating0 Votes
Article ID: iaor2009544
Country: Netherlands
Volume: 178
Issue: 3
Start Page Number: 738
End Page Number: 754
Publication Date: May 2007
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: integer
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.