Approximations to Stochastic Dynamic Programs via Information Relaxation Duality

References

• Adelman D, Mersereau AJ (2008) Relaxations of weakly coupled stochastic dynamic programs. Oper. Res. 56(3):712–727.Link, Google Scholar
• Andersen LM, Broadie M (2004) Primal-dual simulation algorithm for pricing multidimensional American options. Management Sci. 50(9):1222–1234.Link, Google Scholar
• Bertsekas DP (2000) Dynamic Programming and Optimal Control (Athena Scientific, Belmont, MA).Google Scholar
• Blado D, Toriello A (2016) Relaxation analysis for the dynamic knapsack problem with stochastic item sizes. Working paper, Georgia Institute of Technology, Atlanta.Google Scholar
• Blado D, Hu W, Toriello A (2016) Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes. SIAM J. Optim. 26(3):1625–1648.Crossref, Google Scholar
• Borodin A, El-Yaniv R (1998) Online Computation and Competitive Analysis (Cambridge University Press, New York).Google Scholar
• Brown DB, Haugh MB (2017) Information relaxation bounds for infinite horizon Markov decision processes. Oper. Res. 65(5):1355–1379.Link, Google Scholar
• Brown DB, Smith JE (2011) Dynamic portfolio optimization with transaction costs: Heuristics and dual bounds. Management Sci. 57(10):1752–1770.Link, Google Scholar
• Brown DB, Smith JE (2014) Information relaxations, duality, and convex stochastic dynamic programs. Oper. Res. 62(6):1394–1415.Link, Google Scholar
• Brown DB, Smith JE, Sun P (2010) Information relaxations and duality in stochastic dynamic programs. Oper. Res. 58(4-part-1):785–801.Link, Google Scholar
• Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• de Farias DP, Roy BV (2003) The linear programming approach to approximate dynamic programming. Oper. Res. 51(6):850–865.Link, Google Scholar
• Derman C, Lieberman C, Ross S (1978) A renewal decision problem. Management Sci. 24(5):554–561.Link, Google Scholar
• Desai V, Farias VF, Moallemi CC (2012) Pathwise optimization for optimal stopping problems. Management Sci. 58(12):2292–2308.Link, Google Scholar
• Devalkar S, Anupindi R, Sinha A (2011) Integrated optimization of procurement, processing, and trade of commodities. Oper. Res. 59(6):1369–1381.Link, Google Scholar
• Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C (2010) Online stochastic packing applied to display ad allocation. Proc. 18th Annual Eur. Conf. Algorithms: Part I, ESA’10 (Springer-Verlag, Berlin), 182–194.Crossref, Google Scholar
• Garg N, Gupta A, Leonardi S, Sankowski P (2008) Stochastic analyses for online combinatorial optimization problems. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’08 (Society for Industrial and Applied Mathematics, Philadelphia), 942–951.Google Scholar
• Gittins J, Jones D (1974) A dynamic allocation index for the sequential design of experiments. Gani J, ed. Progress in Statistics (North-Holland, Amsterdam), 241–266.Google Scholar
• Grandoni F, Gupta A, Leonardi S, Miettinen P, Sankowski P, Singh M (2008) Set covering with our eyes closed. Proc. Foundations of Comput. Sci. 2008. FOCS ’08. IEEE 49th Annual IEEE Sympos. (IEEE Computer Society, Los Alamitos, CA), 347–356.Crossref, Google Scholar
• Hall LA, Schulz AS, Shmoys DB, Wein J (1997) Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. 22(3):513–544.Link, Google Scholar
• Haugh MB, Kogan L (2004) Pricing American options: A duality approach. Oper. Res. 52(2):258–270.Link, Google Scholar
• Haugh MB, Lim AE (2012) Linear-quadratic control and information relaxations. Oper. Res. Lett. 40(6):521–528.Crossref, Google Scholar
• Haugh MB, Iyengar G, Wang C (2016) Tax-aware dynamic asset allocation. Oper. Res. 64(4):849–866.Link, Google Scholar
• Lai G, Margot F, Secomandi N (2010) An approximate dynamic programming approach to benchmark practice-based heuristics for natural gas storage valuation. Oper. Res. 58(3):564–582.Link, Google Scholar
• Manshadi VH, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res. 37(4):559–573.Link, Google Scholar
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, New York).Google Scholar
• Möhring RH, Schulz AS, Uetz M (1999) Approximation in stochastic scheduling: The power of LP-based priority policies. J. ACM 46(6):924–942.Crossref, Google Scholar
• Nadarajah S, Margot F, Secomandi N (2015) Relaxations of approximate linear programs for the real option management of commodity storage. Management Sci. 61(12):3054–3076.Link, Google Scholar
• Papstavrou JD, Rajagopalan S, Kleywegt AJ (1996) The dynamic and stochastic knapsack problem with deadlines. Management Sci. 42(12):1706–1718.Link, Google Scholar
• Pinedo ML (2012) Scheduling (Springer-Verlag, New York).Crossref, Google Scholar
• Puterman ML (1994) Markov Decision Processes: Discrete Stochastic Dynamic Programming (John Wiley & Sons, New York).Crossref, Google Scholar
• Rogers L (2002) Monte Carlo valuation of American options. Math. Finance 12(3):271–286.Crossref, Google Scholar
• Rogers L (2007) Pathwise stochastic optimal control. SIAM J. Control Optim. 46(3):1116–1132.Crossref, Google Scholar
• Rothkopf M (1966) Scheduling with random service times. Management Sci. 12(9):703–713.Link, Google Scholar
• Skutella M, Sviridenko M, Uetz M (2016) Unrelated machine scheduling with stochastic processing times. Math. Oper. Res. 41(3):851–864.Link, Google Scholar
• Talluri K, van Ryzin G (1998) An analysis of bid-price controls for network revenue management. Management Sci. 44(11):1577–1593.Link, Google Scholar
• Uetz M (2003) When greediness fails: Examples from stochastic scheduling. Oper. Res. Lett. 31(6):413–419.Crossref, Google Scholar
• Vanderbei R (1980) The optimal choice of a subset of a population. Math. Oper. Res. 5(4):481–486.Link, Google Scholar
• Weiss G (1990) Approximation results in parallel machines stochastic scheduling. Ann. Oper. Res. 26(1):195–242.Crossref, Google Scholar
• Weitzman ML (1979) Optimal search for the best alternative. Econometrica 47(3):641–654.Crossref, Google Scholar