An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems
提出一种近似动态规划方法求解多维背包问题，其中一种基于线性规划松弛自适应取整的新启发式算法能快速稳健地获得高质量解，优于CPLEX和遗传算法等现有方法。
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.