A Linear Programming Approach to Nonstationary Infinite-Horizon Markov Decision Processes

References

• Adelman D. Price-directed replenishment of subsets: Methodology and its application to inventory routing. Manufacturing Service Oper. Management (2003) 5(4):348–371Link, Google Scholar
• Adelman D. A price-directed approach to stochastic inventory routing. Oper. Res. (2004) 52(4):499–514Link, Google Scholar
• Adelman D. Dynamic bid-prices in revenue management. Oper. Res. (2007) 55(4):647–661Link, Google Scholar
• Adelman D, Mersereau AJ. Relaxations of weakly coupled stochastic dynamic programs. Oper. Res. (2008) 56(3):712–727Link, Google Scholar
• Aliprantis CD, Border KC. Infinite-Dimensional Analysis: A Hitchhiker's Guide (1994) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Anderson EJ, Nash P. Linear Programming in Infinite-Dimensional Spaces: Theory and Applications (1987) (John Wiley & Sons, Chichester, UK) Google Scholar
• Bean JC, Smith RL. Conditions for the existence of planning horizons. Math. Oper. Res. (1984) 9(3):391–401Link, Google Scholar
• Bean JC, Smith RL. Conditions for the discovery of solution horizons. Math. Programming (1993) 59(2):215–229Crossref, Google Scholar
• Bean JC, Lohmann J, Smith RL. A dynamic infinite horizon replacement economy decision model. Engrg. Economist (1985) 30(2):99–120Crossref, Google Scholar
• Bertsimas D, Tsitsiklis JN. Introduction to Linear Optimization (1997) (Athena Scientific, Belmont, MA) Google Scholar
• Bes C, Sethi S. Concepts of forecast and decision horizons: Application to dynamic stochastic optimization problems. Math. Oper. Res. (1988) 13(2):295–310Link, Google Scholar
• Chand S, Hsu V, Sethi S. Forecast, solution and rolling horizons in operations management problems: A classified bibliography. Manufacturing Service Oper. Management (2002) 4(1):25–43Link, Google Scholar
• Cheevaprawatdomrong T, Smith RL. Infinite horizon production scheduling in time-varying systems under stochastic demand. Oper. Res. (2004) 52(1):105–115Link, Google Scholar
• Cheevaprawatdomrong T, Schochetman IE, Smith RL, Garcia A. Solution and forecast horizons for infinite-horizon non-homogeneous Markov decision processes. Math. Oper. Res. (2007) 32(1):51–72Link, Google Scholar
• Dantzig GB. Linear Programming and Extensions (1963) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• De Farias DP, Van Roy B. The linear programming approach to approximate dynamic programming. Oper. Res. (2003) 51(6):850–865Link, Google Scholar
• de Ghellinck G. Les probléms de décisions séquentielles. Cahiers du Centre d'Etudes de Recherche Opérationnelle (1960) 2:161–179Google Scholar
• D'Epenoux F. A probabilistic production and inventory problem. Management Sci. (1963) 10(1):98–108Link, Google Scholar
• Federgruen A, Tzur M. Fast solution and detection of minimal forecast horizons in dynamic programs with a single indicator of future: Application to dynamic lot-sizing models. Management Sci. (1995) 41(5):874–893Link, Google Scholar
• Garcia A, Smith RL. Solving nonstationary infinite horizon dynamic optimization problems. J. Math. Anal. Appl. (2000) 244(2):304–317Crossref, Google Scholar
• Ghate A, Cochran J. Infinite horizon problems. Wiley Encyclopedia of Operations Research and Management Science (2011) (John Wiley & Sons, Hoboken, NJ) Crossref, Google Scholar
• Ghate A, Smith RL. Characterizing extreme points as basic feasible solutions in infinite linear programs. Oper. Res. Lett. (2009a) 37(1):7–10Crossref, Google Scholar
• Ghate A, Smith RL. Optimal backlogging over an infinite horizon under time varying convex production and inventory costs. Manufacturing Service Oper. Management (2009b) 11(2):362–368Link, Google Scholar
• Ghate A, Sharma D, Smith RL. A shadow simplex method for infinite linear programs. Oper. Res. (2010) 58(4):865–877Link, Google Scholar
• Grinold RC. Finite horizon approximations of infinite horizon linear programs. Math. Programming (1977) 12(1):1–17Crossref, Google Scholar
• Hernandez-Lerma O. Adaptive Markov Control Processes (1989) (Springer, New York) Crossref, Google Scholar
• Hernandez-Lerma O, Lasserre JB. A forecast horizon and a stopping rule for general Markov decision processes. J. Math. Anal. Appl. (1988) 132(2):388–400Crossref, Google Scholar
• Hernandez-Lerma O, Lasserre JB, Feinberg E, Shwartz A. The linear programming approach. Handbook of Markov Decision Processes: Methods and Algorithms (2002) (Kluwer, Boston) 377–408Chap. 12Crossref, Google Scholar
• Hopp W. Identifying forecast horizons in nonhomogeneous Markov decision processes. Oper. Res. (1989) 37(2):339–343Link, Google Scholar
• Hopp WJ, Bean JC, Smith RL. A new optimality criterion for non-homogeneous Markov decision processes. Oper. Res. (1987) 35(6):875–883Link, Google Scholar
• Howard RA. Dynamic programming and Markov processes. (1960) . Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Kunnumkal S, Topaloglu H. A duality-based relaxation and decomposition approach for inventory distribution systems. Naval Res. Logist. (2008) 55(7):612–631Crossref, Google Scholar
• Manne AS. Linear programming and sequential decisions. Management Sci. (1960) 6(3):259–267Link, Google Scholar
• Munkres JR. Topology (2000) (Prentice-Hall, Upper Saddle River, NJ) Google Scholar
• Patrick J, Puterman ML, Queyranne M. Dynamic multi-priority patient scheduling for a diagnostic resource. Oper. Res. (2008) 56(6):1507–1525Link, Google Scholar
• Powell WB. Approximate Dynamic Programming: Solving the Curses of Dimensionality (2007) (John Wiley & Sons, Hoboken, NJ) Crossref, Google Scholar
• Puterman ML. Markov Decision Processes: Discrete Stochastic Dynamic Programming (1994) (John Wiley & Sons, Hoboken, NJ) Crossref, Google Scholar
• Romeijn HE, Smith RL. Shadow prices in infinite dimensional linear programming. Math. Oper. Res. (1998) 23(1):239–256Link, Google Scholar
• Romeijn HE, Sharma D, Smith RL. Extreme point solutions for infinite network flow problems. Networks (2006) 48(4):209–222Crossref, Google Scholar
• Romeijn HE, Smith RL, Bean JC. Duality in infinite dimensional linear programming. Math. Programming (1992) 53(1–3):79–97Crossref, Google Scholar
• Ross SM. Introduction to Stochastic Dynamic Programming (1983) (Academic Press, New York) Google Scholar
• Schochetman IE, Smith RL. Finite dimensional approximation in infinite dimensional mathematical programming. Math. Programming (1992) 54(3):307–333Crossref, Google Scholar
• Sharkey TC, Romeijn HE. A simplex algorithm for minimum cost network flow problems in infinite networks. Networks (2008) 52(1):14–31Crossref, Google Scholar
• Smith RL, Zhang R. Infinite horizon production planning in time varying systems with convex production and inventory costs. Management Sci. (1998) 44(9):1313–1320Link, Google Scholar
• Topaloglu H. Using Lagrangian relaxation to compute capacity-dependent bid prices in network revenue management. Oper. Res. (2009) 57(3):637–649Link, Google Scholar
• Topaloglu H, Powell WB. A distributed decision-making structure for dynamic resource allocation using nonlinear functional approximations. Oper. Res. (2005) 53(2):281–297Link, Google Scholar
• Topaloglu H, Powell WB. Sensitivity analysis of a dynamic fleet management model using approximate dynamic programming. Oper. Res. (2007) 55(2):319–331Link, Google Scholar
• Tseng P. Solving h-horizon, stationary Markov decision problems in time proportional to log(h). Oper. Res. Lett. (1990) 9(5):287–297Crossref, Google Scholar
• Ye Y. A new complexity result on solving the Markov decision problem. Math. Oper. Res. (2005) 30(3):733–749Link, Google Scholar
• Ye Y. The simplex and policy iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. (2011) . Technical report, Stanford University. http://www.stanford.edu/~yyye/SimplexMDP4.pdfGoogle Scholar
• Zhang D, Adelman D. An approximate dynamic programming approach to network revenue management with customer choice. Transportation Sci. (2009) 43(3):381–394Link, Google Scholar