Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first last
cannonical link button


Control and Cybernetics

Tytuł artykułu

Approximating the solution of a dynamic, stochastic multiple knapsack problem

Autorzy Hartman, J. C.  Perry, T. C. 
Treść / Zawartość
Warianty tytułu
Języki publikacji EN
EN We model an environment where orders arrive probabilistically over time, with their revenues and capacity requirements becoming known upon arrival. The decision is whether to accept an order, receiving a reward and reserving capacity, or reject an order, freeing capacity for possible future arrivals. We model the dynamic, stochastic multiple knapsack problem (DSMKP) with stochastic dynamic programming (SDP). Multiple knapsacks are used as orders may stay in the system for multiple periods. As the state space grows exponentially in the number of knapsacks and the number of possible orders per period, we utilize linear programming and duality to quickly approximate the end-of-horizon values for the SDP. This helps mitigate end-of-study effects when solving the SDP directly, allowing for the solution of larger problems and leading to increased quality in solutions.
Słowa kluczowe
PL programowanie liniowe   dualność  
EN stochastic dynamic programming   approximate dynamic programming   linear programming   duality  
Wydawca Systems Research Institute, Polish Academy of Sciences
Czasopismo Control and Cybernetics
Rocznik 2006
Tom Vol. 35, no 3
Strony 535--550
Opis fizyczny Bibliogr. 11 poz., rys., wykr.
autor Hartman, J. C.
autor Perry, T. C.
  • Industrial and Systems Engineering, Lehigh University, Bethlehem, Pennsylvania, USA
BELLMAN, R.E. (1957) Dynamic Programming. Princeton University Press. Princeton, NJ.
BERTSEKAS, D.P. and TSITSIKLIS, J. (1996) Neuro-Dynamic Programming. Athena Scientific.
BERTSIMAS, D. and DEMIR. R. (2002) An approximate dynamic programming approach to multidimensional knapsack problems. Management Science 48(4), 550-565.
DE FARIAS, D.P. and VAN ROY, B. (2003) The linear programming approach to approximate dynamic programming. Operations Research 51, 850-865.
GODFREY, G. and POWELL, W.B. (2002) An adaptive, distribution-free algorithm for the newsvendor problem with censored demands, with application to inventory and distribution problems. Management Science 47(8), 1101-1112.
JOHNSON, S.A., SHOEMAKER, C.A., STEDINGER. J.R., LI, Y. and TEJADA-GUIBERT, J.A. (1993) Numerical solutions of continuous-state dynamic progams using linear and spline interpolation. Operations Research 41. 484-500.
PERRY, T.C. and HARTMAN, J.C. (2004) Allocating manufacturing capacity by solving a dynamic, stochastic, multiple knapsack problem. Technical Report T004-009, Industrial and Systems Engineering, Lehigh University, Bethlehem, PA.
PHILBRICK, R. and KITANIDIS, P.K. (2001) Improved dynamic programming methods for optimal control of lumped parameter stochastic systems. Operations Research 49, 398-412.
POWELL, W.B. and CARVALHO, T. (1998) Dynamic control of logistics queueing networks for large scale fle et management. Transportation Science 32(2), 90-109.
SHAPIRO, J., POWELL, W.B. and SIMAO, H.P. (2002) An adaptive, dynamic programming algorithm for the heterogeneous resource allocation problem. Transportation Science 36(2), 231-249.
TOPALOGLU, H. and POWELL, W.B. (2006) Dynamic programming approximations for stochastic, time-staged integer multicommodity flow problems. INFORMS Journal on Computing.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-BAT5-0013-0002