Institutional Repository

Cardinality constrained 0-1 Knapsack problems

Show simple item record Kruger, MF Hattingh, JM Steyn, T
dc.contributor.editor Venter, L
dc.contributor.editor Lombard, R.R. 2018-09-10T13:04:10Z 2018-09-10T13:04:10Z 2000
dc.identifier.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) en
dc.identifier.isbn 1-86822-300-0
dc.description.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. en
dc.language.iso en en
dc.title Cardinality constrained 0-1 Knapsack problems en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UnisaIR


My Account