Premium
An approximate dynamic programming approach to solving a dynamic, stochastic multiple knapsack problem
Author(s) -
Perry Thomas C.,
Hartman Joseph C.
Publication year - 2009
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2008.00679.x
Subject(s) - knapsack problem , dynamic programming , mathematical optimization , recursion (computer science) , stochastic programming , change making problem , computer science , time horizon , continuous knapsack problem , set (abstract data type) , reservation , mathematics , algorithm , computer network , programming language
We model a multiperiod, single resource capacity reservation problem as a dynamic, stochastic, multiple knapsack problem with stochastic dynamic programming. As the state space grows exponentially in the number of knapsacks and the decision set grows exponentially in the number of order arrivals per period, the recursion is computationally intractable for large‐scale problems, including those with long horizons. Our goal is to ensure optimal, or near optimal, decisions at time zero when maximizing the net present value of returns from accepted orders, but solving problems with short horizons introduces end‐of‐study effects which may prohibit finding good solutions at time zero. Thus, we propose an approximation approach which utilizes simulation and deterministic dynamic programming in order to allow for the solution of longer horizon problems and ensure good time zero decisions. Our computational results illustrate the effectiveness of the approximation scheme.