 Methods for the Solution of the Multidimensional 0/1 Knapsack ProblemH. Martin Weingartner and
David N. Ness
Operations Research, 1967, vol. 15, issue 1, 83-103 Abstract: In the knapsack problem, given the desirability of each of a number of items, one seeks to find that subset which satisfies a constraint on total weight. The multidimensional variant imposes constraints on additional variables of the items; the 0/1 specification means that an item is either taken or not, i.e., multiples of the same item are not considered, except possibly indirectly. Traditionally the one-dimensional knapsack problem is solved by means of dynamic programming. The multidimensional problem is usually reduced to a one-dimensional one by use of Lagrangian Multipliers that, however, do not generally yield the exact solution to the problem posed. Here some new algorithms are developed that are applied within a dynamic programming framework. Additionally, the methods make integral use of an interactive computer system in which the heuristics of the problem solver are applied and changed as the character of the solution process evolves. The problem arises in the context of capital budgeting, but has obvious applications in a variety of other areas. The methods have been employed for solving numerical problems with as many as 105 items, the parameters having been obtained from industrial applications. Date: 1967 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:15:y:1967:i:1:p:83-103 Access Statistics for this article More articles in Operations Research from INFORMS Contact information at EDIRC. |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.