A new lower bound for the linear knapsack problem with general integer variables
In: European Journal of Operational Research, Jg. 178 (2007-05-01), S. 738-754
Online
unknown
Zugriff:
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.
Titel: |
A new lower bound for the linear knapsack problem with general integer variables
|
---|---|
Autor/in / Beteiligte Person: | Mathur, Kamlesh ; Venkateshan, Prahalad |
Link: | |
Zeitschrift: | European Journal of Operational Research, Jg. 178 (2007-05-01), S. 738-754 |
Veröffentlichung: | Elsevier BV, 2007 |
Medientyp: | unknown |
ISSN: | 0377-2217 (print) |
DOI: | 10.1016/j.ejor.2006.02.018 |
Schlagwort: |
|
Sonstiges: |
|