Note---An Approximate Algorithm for Multidimensional Zero-One Knapsack Problems---A Parametric Approach

Jae Sik Lee and Monique Guignard
Additional contact information
Jae Sik Lee: The Wharton School, University of Pennsylvania, Philadelphia, Pennsylvania 19104
Monique Guignard: The Wharton School, University of Pennsylvania, Philadelphia, Pennsylvania 19104

Management Science, 1988, vol. 34, issue 3, 402-410

Abstract: A new approximate algorithm for multidimensional zero-one knapsack problems with all positive coefficients is presented. The procedure is controlled by three parameters which affect the tradeoff between solution quality and computation time and whose values are set by the users. For 48 test problems with 5 to 20 constraints and 6 to 500 variables, the solution found was on the average within 0.34% of the optimum and the computation time was the shortest compared with three other well-known heuristics.

Keywords: programming: integer algorithms; heuristic (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.3.402 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:34:y:1988:i:3:p:402-410

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().