An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems

Dimitris Bertsimas () and Ramazan Demir ()
Additional contact information
Dimitris Bertsimas: Sloan School of Management and Operations Research Center, E53-363, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Ramazan Demir: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Management Science, 2002, vol. 48, issue 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.

Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (27)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.48.4.550.208 (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:48:y:2002:i:4:p:550-565

Access Statistics for this article

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