List of Knapsack Problems: 2 Multiple Constraints

List of knapsack problems
Given a set of n items N = {1, . . . , n} and

a set of m so-called elements P = {1, . . . , m}
, each item j corresponds to a subset Pj of the
element set P . The items j have non-negative
prots pj , j = 1, . . . , n , and the elements i
have non-negative weights wi , i = 1, . . . , m .
The total weight of a set of items is given by the
total weight of the elements of the union of the
corresponding element sets. The objective is to
nd a subset of the items with total weight not
exceeding the knapsack capacity and maximal
prot.
The knapsack problem is one of the most studied problems in combinatorial optimization, with many real-life
applications. For this reason, many special cases and generalizations have been examined.
Common to all versions are a set of n items, with each
item 1 j n having an associated prot pj ,weight wj.
The binary decision variable xj is used to select the item.
The objective is to pick some of the items, with maximal
total prot, while obeying that the maximum total weight
of the chosen items must not exceed W. Generally, these
coecients are scaled to become integers, and they are
almost always assumed to be positive.
The knapsack problem in its most basic form:
2 Multiple constraints
1
If there is more than one constraint (for example, both a

volume limit and a weight limit, where the volume and
weight of each item are not related), we get the multiply constrained knapsack problem, multidimensional
knapsack problem, or m-dimensional knapsack problem. (Note, dimension here does not refer to the shape
of any items.) This has 0-1, bounded, and unbounded
variants; the unbounded one is shown below.
Direct generalizations
One common variant is that each item can be chosen multiple times. The bounded knapsack problem species,
for each item j, an upper bound uj (which may be a positive integer, or innity) on the number of times item j can
be selected:
The unbounded knapsack problem (sometimes called The 0-1 variant (for any xed m 2 ) was shown to
the integer knapsack problem) does not put any upper be NP-complete around 1980 and more strongly, has no
bounds on the number of times an item may be selected: FPTAS unless P=NP.[3][4]
The bounded and unbounded variants (for any xed m
2 ) also exhibit the same hardness.[5]
The unbounded variant was shown to be NP-complete

in 1975 by Lueker.[1] Both the bounded and unbounded
variants admit an FPTAS (essentially the same as the one
used in the 0-1 knapsack problem).
For any xed m 2 , these problems do admit a pseudopolynomial time algorithm (similar to the one for basic
If the items are subdivided into k classes denoted Ni , knapsack) and a PTAS.[2]
and exactly one item must be taken from each class, we
get the multiple-choice knapsack problem:
If for each item the prots and weights are identical, we 3 Knapsack-like problems
get the subset sum problem (often the corresponding
decision problem is given instead):
If all the prots are 1, we can try to minimize the number
If we have n items and m knapsacks with capacities Wi , of items which exactly ll the knapsack:
we get the multiple knapsack problem:
If we have a number of containers (of the same size), and
As a special case of the multiple knapsack problem, when we wish to pack all n items in as few containers as possithe prots are equal to weights and all bins have the same ble, we get the bin packing problem, which is modelled
by having indicator variables yi = 1 container i is
capacity, we can have multiple subset sum problem.
being used:
Quadratic knapsack problem:
The cutting stock problem is identical to the bin packSet-Union Knapsack Problem:
ing problem, but since practical instances usually have far
SUKP is dened by Kellerer et al[2] (on page 423) as fol- fewer types of items, another formulation is often used.
lows:
Item j is needed Bj times, each pattern of items which
1
t into a single knapsack have a variable, xi (there are m

patterns), and pattern i uses item j bij times:
If, to the multiple choice knapsack problem, we add the
constraint that each subset is of size n and remove the restriction on total weight, we get the assignment problem,
which is also the problem of nding a maximal bipartite
matching:
In the Maximum Density Knapsack variant there is an
initial weight w0 , and we maximize the density of selected of items which do not violate the capacity constraint: [6]
Although less common than those above, several other
knapsack-like problems exist, including:
Nested knapsack problem
Collapsing knapsack problem
Nonlinear knapsack problem
Inverse-parametric knapsack problem
The last three of these are discussed in Kellerer et als
reference work, Knapsack Problems.[2]
References
[1] Lueker, G.S. (1975). Report No. 178, Computer Science Laboratory, Princeton. |chapter= ignored (help)
[2] Kellerer, Hans and Pferschy, Ulrich and Pisinger, David
(2004). Knapsack Problems. Springer Verlag. ISBN 3540-40286-1.
[3] Gens, G. V. and Levner, E. V. (1979). Complexity and
Approximation Algorithms for Combinatorial Problems:
A Survey. Central Economic and Mathematical Institute,
Academy of Sciences of the USSR, Moscow.
[4] On the Existence of Fast Approximation Schemes.
Nonlinear Programming (Academic Press) 4: 415437.
1980.
[5] Magazine, M. J.; Chern, M.-S. (1984). A Note on
Approximation Schemes for Multidimensional Knapsack
Problems. Mathematics of Operations Research 9 (2):
244247. doi:10.1287/moor.9.2.244.
[6] Cohen, R. and Katzir, L. 2008. The Generalized Maximum Coverage Problem. Inf. Process. Lett. 108, 1 (Sep.
2008), 15-22.
Algorithms for Knapsack Problems, D. Pisinger.

Ph.D. thesis, DIKU, University of Copenhagen, Report 95/1 (1995).
REFERENCES
Text and image sources, contributors, and licenses
5.1
Text
List of knapsack problems Source: http://en.wikipedia.org/wiki/List_of_knapsack_problems?oldid=618134260 Contributors: Gandalf61, DerekLaw, LOL, Rjwilmsi, New Thought, Yahya Abdal-Aziz, Arthur Rubin, Benandorsqueaks, Melchoir, Chris the speller, Squamate, Xelnaga diku, BlueLint, LiranKatzir, DiscX, Volkan YAZICI, Daveagp, Addbot, LaaknorBot, SaddleAdam, Yobot, Citation bot,
Citation bot 1, Trappist the monk, RjwilmsiBot, Joerg Bader, Ynayeb, Tzhai and Anonymous: 17
5.2
Images
5.3
Content license
Creative Commons Attribution-Share Alike 3.0

List of Knapsack Problems: 2 Multiple Constraints

Uploaded by

Copyright:

Available Formats

List of Knapsack Problems: 2 Multiple Constraints

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

List of Knapsack Problems: 2 Multiple Constraints

Uploaded by

Copyright:

Available Formats

List of knapsack problems

Given a set of n items N = {1, . . . , n} and

If there is more than one constraint (for example, both a

The unbounded variant was shown to be NP-complete

t into a single knapsack have a variable, xi (there are m

Algorithms for Knapsack Problems, D. Pisinger.

Text and image sources, contributors, and licenses

Creative Commons Attribution-Share Alike 3.0

You might also like