search query: @indexterm DYNAMIC MODELS / total: 269
reference: 30 / 269
Author: | Bertsimas, D. Demir, R. |
Title: | An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems |
Journal: | Management Science
2002 : APR, VOL. 48:4, p. 550-565 |
Index terms: | DYNAMIC PROGRAMMING DYNAMIC MODELS PROBLEM SOLVING ANALYTICAL REVIEW |
Language: | eng |
Abstract: | The authors present an Approximate Dynamic Programming (ADP) approach for the multidimensional knapsack problem (MKP). The authors approximate the value function (a) using parametric and nonparametric methods and (b) using a base-heuristic. The authors propose a new heuristic which adaptively rounds the solution of the linear programming relaxation. The authors' 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. |
SCIMA