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

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.

• 저널Management Science · 34(3) · 402–410
• 토픽Optimization and Packing Problems · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.34.3.402
• 저자Jae Sik Lee, Monique Guignard