Cardinality constrained 0-1 Knapsack problems
Loading...
Authors
Kruger, MF
Hattingh, JM
Steyn, T
Issue Date
2000
Type
Language
en
Keywords
Alternative Title
Abstract
The Knapsack Problem is one of the most important problems in Discrete
optimization. Although it is the simplest integer program, it has numerous practical
applications and often appears as a subproblem in solving more complicated
problems.
Inspired by recent research results we take a closer look at a new emerging
problem , the cardinality constrained 0- 1 knapsack problem. If one knows the
cardinality (i.e. the number of items packed into the knapsack) of an optimal solution
one can solve the equivalent problem where the cardinality constraint is an equality
constraint. We propose an exact algorithm based on Lagrangian relaxation for this
problem. We introduce a specialized iterative, but finite, technique for determining
the optimal Lagrange multipliers and report on the results of numerical experiments
with our algorithm.
Description
Citation
Kruger, M.F., Hattingh, J.M. & Steyn, T. (1997) Cardinality constrained 0-1 Knapsack problems. Proceedings of the 1997 National Research and Development Conference: Towards 2000, South African Institute of Computer Science and Information Technology), Riverside Sun, 13-14 November, 2000, edited by L.M. Venter and R.R. Lombard (PUCHEE, VTC)