An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems
Authors:
- 1 April 2002
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 48 (4) , 550-565
Abstract
We present an Approximate Dynamic Programming (ADP) approach for the multidimensional knapsack problem (MKP). We approximate the value function (a) using parametric and nonparametric methods and (b)using a base-heuristic. We propose a new heuristic which adaptively rounds the solution of the linear programming relaxation. Our computational study suggests: (a)the new heuristic produces high quality solutions fast and robustly, (b)state of the art commercial packages like CPLEX require significantly larger computational time to achieve the same quality of solutions, (c) the ADP approach using the new heuristic competes successfully with alternative heuristic methods such as genetic algorithms, (d)the ADP approach based on parametric and nonparametric approximations, while producing reasonable solutions, is not competitive. Overall, this research illustrates that the base-heuristic approach is a promising computational approach for MKPs worthy of further investigation.Keywords
This publication has 32 references indexed in Scilit:
- A Genetic Algorithm for the Multidimensional Knapsack ProblemJournal of Heuristics, 1998
- Rollout Algorithms for Combinatorial OptimizationJournal of Heuristics, 1997
- An efficient preprocessing procedure for the multidimensional 0–1 knapsack problemDiscrete Applied Mathematics, 1994
- Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement HeuristicINFORMS Journal on Computing, 1994
- Some integer programs arising in the design of main frame computersMathematical Methods of Operations Research, 1993
- Probabilistic Analysis of the Multidimensional Knapsack ProblemMathematics of Operations Research, 1989
- Heuristics and reduction methods for multiple constraints 0–1 linear programming problemsEuropean Journal of Operational Research, 1986
- Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimalityMathematical Programming, 1985
- Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analysesEuropean Journal of Operational Research, 1984
- A HEURISTIC FOR GENERAL INTEGER PROGRAMMING*Decision Sciences, 1974