zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Where are the hard knapsack problems? (English) Zbl 1116.90089
Summary: The knapsack problem is believed to be one of the “easier” $NP$-hard problems. Not only can it be solved in pseudo-polynomial time, but also decades of algorithmic improvements have made it possible to solve nearly all standard instances from the literature. The purpose of this paper is to give an overview of all recent exact solution approaches, and to show that the knapsack problem still is hard to solve for these algorithms for a variety of new test problems. These problems are constructed either by using standard benchmark instances with larger coefficients, or by introducing new classes of instances for which most upper bounds perform badly. The first group of problems challenge the dynamic programming algorithms while the other group of problems are focused towards branch-and-bound algorithms. Numerous computational experiments with all recent state-of-the-art codes are used to show that (KP) is still difficult to solve for a wide number of problems. One could say that the previous benchmark tests were limited to a few highly structured instances, which do not show the full characteristics of knapsack problems.

90C27Combinatorial optimization
90C39Dynamic programming
90C57Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI
[1] Martello, S.; Pisinger, D.; Toth, P.: New trends in exact algorithms for the 0--1 knapsack problem. European journal of operational research 123, 325-332 (2000) · Zbl 0961.90090
[2] Kellerer, H.; Pferschy, U.; Pisinger, D.: Knapsack problems. (2004) · Zbl 1103.90003
[3] Meyer Auf Der Heide, F.: A polynomial linear search algorithm for the n-dimensional knapsack problem. Journal of the ACM 31, 668-676 (1984) · Zbl 0631.68037
[4] Fournier H, Koiran P. Are lower bounds easier over the reals? In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), 1998. p. 507--13. · Zbl 1028.68051
[5] Balas, E.; Zemel, E.: An algorithm for large zero-one knapsack problems. Operations research 28, 1130-1154 (1980) · Zbl 0449.90064
[6] Martello, S.; Toth, P.: A new algorithm for the 0--1 knapsack problem. Management science 34, 633-644 (1988) · Zbl 0645.90054
[7] Pisinger, D.: An expanding-core algorithm for the exact 0--1 knapsack problem. European journal of operational research 87, 175-187 (1995) · Zbl 0914.90199
[8] Martello, S.; Toth, P.: Upper bounds and algorithms for hard 0--1 knapsack problems. Operations research 45, 768-778 (1997) · Zbl 0902.90125
[9] Bellman, R. E.: Dynamic programming. (1957) · Zbl 0077.13605
[10] Pisinger, D.: Dynamic programming on the word RAM. Algorithmica 35, 128-145 (2003) · Zbl 1033.90145
[11] Pisinger, D.: Linear time algorithms for knapsack problems with bounded weights. Journal of algorithms 33, 1-14 (1999) · Zbl 0951.90047
[12] Pisinger, D.: A minimal algorithm for the 0--1 knapsack problem. Operations research 45, 758-767 (1997) · Zbl 0902.90126
[13] Martello, S.; Pisinger, D.; Toth, P.: Dynamic programming and strong bounds for the 0--1 knapsack problem. Management science 45, 414-424 (1999) · Zbl 1231.90338
[14] Martello, S.; Toth, P.: Knapsack problems: algorithms and computer implementations. (1990) · Zbl 0708.68002
[15] Pisinger, D.: Core problems in knapsack algorithms. Operations research 47, 570-575 (1999) · Zbl 0979.90091
[16] Weismantel, R.: On the 0/1 knapsack polytope. Mathematical programming 77, 49-68 (1997) · Zbl 0891.90130