Technical Note—On the Strength of Relaxations of Weakly Coupled Stochastic Dynamic Programs

References

• Adelman D (2004) A price-directed approach to stochastic inventory/routing. Oper. Res. 52(4):499–514.Link, Google Scholar
• Adelman D (2007) Dynamic bid prices in revenue management. Oper. Res. 55(4):647–661.Link, Google Scholar
• Adelman D, Mersereau AJ (2008) Relaxations of weakly coupled stochastic dynamic programs. Oper. Res. 56(3):712–727.Link, Google Scholar
• Balseiro SR, Brown DB, Chen C (2021) Dynamic pricing of relocating resources in large networks. Management Sci. 67(7):4075–4094.Link, Google Scholar
• Bertsimas D, Mersereau AJ (2007) A learning approach for interactive marketing to a customer segment. Oper. Res. 55(6):1120–1135.Link, Google Scholar
• Bertsimas D, Mišíc VV (2016) Decomposable Markov decision processes: A fluid optimization approach. Oper. Res. 64(6):1537–1555.Link, Google Scholar
• Brown DB, Smith JE (2020) Index policies and performance bounds for dynamic selection problems. Management Sci. 66(7):3029–3050.Link, Google Scholar
• Caro F, Gallien J (2007) Dynamic assortment with demand learning for seasonal consumer goods. Management Sci. 53(2):276–292.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
• Dentcheva D, Römisch W (1998) Optimal power generation under uncertainty via stochastic programming. Marti K, Kall P, eds. Stochastic Programming Methods and Technical Applications (Springer, Berlin), 22–56.Crossref, Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. FOCS '09: Proc. 2009 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 117–126.Google Scholar
• Geoffrion A (1974) Lagrangean relaxation for integer programming. Math. Programming Stud. 2:82–114.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197.Crossref, Google Scholar
• Hawkins JT (2003) A Langrangian decomposition approach to weakly coupled dynamic optimization problems and its applications. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Heller I, Tompkins CB (1956) An extension of a theorem of Dantzig’s. Kuhn HW, Tucker AW, eds. Linear Inequalities and Related Systems, vol. 38 (Princeton University Press, Princeton, NJ), 247–254.Google Scholar
• Hu W, Frazier P (2017) An asymptotically optimal index policy for finite-horizon restless bandits. Preprint, submitted July 1, https://arxiv.org/abs/1707.00205.Google Scholar
• Kunnumkal S, Talluri K (2016) On a piecewise-linear approximation for network revenue management. Math. Oper. Res. 41(1):72–91.Link, Google Scholar
• Lin EY-H (1998) A bibliographical survey on some well-known non-standard knapsack problems. INFOR Inform. Systems Oper. Res. 36(4):274–317.Crossref, Google Scholar
• Maxwell MS, Restrepo M, Henderson SG, Topaloglu H (2010) Approximate dynamic programming for ambulance redeployment. INFORMS J. Comput. 22(2):266–281.Link, Google Scholar
• Miao S, Jasin S, Chao X (2022) Asymptotically optimal Lagrangian policies for multi-warehouse, multi-store systems with lost sales. Oper. Res. 70(1):141–159.Link, Google Scholar
• Puterman ML (1994) Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1st ed. (John Wiley & Sons, Inc., Hoboken, NJ).Crossref, Google Scholar
• Schweitzer PJ, Seidmann A (1985) Generalized polynomial approximations in Markovian decision processes. J. Math. Anal. Appl. 110(2):568–582.Crossref, Google Scholar
• Sinha P, Zoltners AA (1979) The multiple-choice knapsack problem. Oper. Res. 27(3):503–515.Link, Google Scholar
• Takriti S, Birge JR (2000) Lagrangian solution techniques and bounds for loosely coupled mixed-integer stochastic programs. Oper. Res. 48(1):91–98.Link, Google Scholar
• Topaloglu H (2009) Using Lagrangian relaxation to compute capacity-dependent bid prices in network revenue management. Oper. Res. 57(3):637–649.Link, Google Scholar
• Vossen TW, Zhang D (2015) Reductions of approximate linear programs for network revenue management. Oper. Res. 63(6):1352–1371.Link, Google Scholar
• Whittle P (1980) Multi-armed bandits and the Gittins index. J. Roy. Statist. Soc. B 42(2):143–149.Google Scholar
• Whittle P (1988) Restless bandits: Activity allocation in a changing world. J. Appl. Probab. 25:287–298.Crossref, Google Scholar
• Zayas-Caban G, Jasin S, Wang G (2019) An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits. Adv. Appl. Probab. 51(3):745–772.Crossref, Google Scholar