article

Stochastic Depletion Problems: Effective Myopic Policies for a Class of Dynamic Optimization Problems

Authors:

Vivek F. FariasAuthors Info & Claims

Mathematics of Operations Research, Volume 34, Issue 2

Pages 333 - 350

https://doi.org/10.1287/moor.1080.0364

Published: 01 May 2009 Publication History

Abstract

This paper presents a general class of dynamic stochastic optimization problems we refer to as stochastic depletion problems. A number of challenging dynamic optimization problems of practical interest are stochastic depletion problems. Optimal solutions for such problems are difficult to obtain, both from a pragmatic computational perspective as well as from a theoretical perspective. As such, simple heuristics are desirable. We isolate two simple properties that, if satisfied by a problem within this class, guarantee that a myopic policy incurs a performance loss of at most 50% relative to the optimal adaptive control policy for that problem. We are able to verify that these two properties are satisfied for several interesting families of stochastic depletion problems and, as a consequence, we identify computationally efficient approximations to optimal control policies for a number of interesting dynamic stochastic optimization problems.

References

[1]

Bar-Noy, A., Guha, S., Katz, Y., Naor, J., Schieber, B. and Shachnai, H., "Throughput maximization of real-time scheduling with batching," Proc. 13th SODA, pp. 742-751, 2002.

Digital Library

[2]

Bassamboo, A., Harrison, J. M. and Zeevi, A., "Design and control of a large call center: Asymptotic analysis of an LP-based method," Oper. Res., v54, pp. 419-435, 2006.

Digital Library

[3]

Bassamboo, A., Harrison, J. M. and Zeevi, A., "Dynamic routing and admission control in high volume service systems: Asymptotic analysis via multi-scale fluid limits," Queueing Systems Theory Appl., v51, pp. 249-285, 2006.

Digital Library

[4]

Buyukkoc, C., Varaiya, P. and Walrand, J., "The c-μ rule revisited," Adv. Appl. Probab., v17, pp. 237-238, 1985.

[5]

Calinescu, G., Chekuri, G., Pál, M. and Vondrák, J., "Maximizing a submodular set function subject to a matroid constraint," Proc. 12th IPCO, pp. 182-196, 2007.

Digital Library

[6]

Chou, P. A. and Miao, Z., "Rate-distortion optimized streaming of packetized media," IEEE Trans. Multimedia, v8, pp. 390-404, 2006.

Digital Library

[7]

Dua, A. and Bambos, N., "Downlink scheduling of heterogeneous traffic," Proc. IEEE ICC, v11, pp. 5252-5257, 2006.

[8]

Dua, A. and Bambos, N., "Joint power allocation and scheduling for deadline constrained wireless traffic," Proc. IEEE Globecom, pp. 1-5, 2006.

[9]

Dua, A. and Bambos, N., "Downlink wireless packet scheduling with deadlines," IEEE Trans. Mobile Comput., v6, pp. 1410-1425, 2007.

Digital Library

[10]

Eryilmaz, A., Srikant, R. and Perkins, J. R., "Stable scheduling policies for fading wireless channels," IEEE/ACM Trans. Netw., v13, pp. 411-424, 2005.

Digital Library

[11]

Fisher, M. L., Nemhauser, G. L. and Wolsey, L. A., "An analysis of approximations for maximizing submodular set functions---II," Math. Programming Study, v8, pp. 73-87, 1978.

[12]

Fleischer, L. K., Goemans, M. X., Mirrokni, V. and Sviridenko, M., "Tight approximation algorithms for maximizing general assignment problems," Proc. 17th SODA, pp. 611-620, 2006.

Digital Library

[13]

Frank, R. E., Massy, W. F. and Wind, Y., Market Segmentation, Prentice-Hall, Englewood Cliffs, NJ, 1972.

[14]

Gandhi, T., Khuller, S., Parthasarathy, S. and Srinivasan, A., "Dependent rounding in bipartite graphs," Proc. 43rd FOCS, pp. 323-332, 2002.

Digital Library

[15]

Goundan, P. R. and Schulz, A. S., "Revisiting the greedy approach to submodular set function maximization," 2007.

[16]

Harrison, J. M. and Zeevi, A., "A method for staffing large call centers using stochastic fluid models," Manufacturing Service Oper. Management, v7, pp. 20-36, 2005.

Digital Library

[17]

Hopp, W. J. and Xu, X., "Product line selection and pricing with modularity," Manufacturing Service Oper. Management, v7, pp. 172-187, 2005.

Digital Library

[18]

Huang, J., Berry, R. and Honig, M., "Wireless scheduling with hybrid ARQs," IEEE Trans. Wireless Comm., v4, pp. 2801-2810, 2005.

Digital Library

[19]

Jansen, K. and Zhang, G., "On rectangle packing: Maximizing benefits," Proc. 17th SODA, pp. 204-213, 2004.

Digital Library

[20]

Kim, J.-H. and Chwa, K.-Y., "Scheduling broadcasts with deadlines," Theoretical Comput. Sci., v325, pp. 479-488, 2004.

Digital Library

[21]

Kohli, R. and Sukumar, R., "Heuristics for product-line design using conjoint analysis," Management Sci., v36, pp. 1464-1478, 1990.

Digital Library

[22]

Moorthy, K. S., "Market segmentation, self-selection, and product line design," Marketing Sci., v3, pp. 288-307, 1984.

Digital Library

[23]

Nemhauser, G. L., Wolsey, L. A. and Fisher, M. L., "An analysis of approximations for maximizing submodular set functions---I," Math. Programming, v14, pp. 265-294, 1978.

Digital Library

[24]

Pigou, A. C., The Economics of Welfare, AMS Press, Inc., NY, 1978.

[25]

Ren, T., Koutsopoulos, I. and Tassiulas, L., "QoS provisioning for real-time traffic in wireless packet networks," Proc. IEEE GLOBECOM, v2, pp. 1673-1677, 2002.

[26]

Shmoys, D. B. and Tardos, E., "An approximation algorithm for the generalized assignment problem," Math. Programming, v62, pp. 461-474, 1993.

Digital Library

[27]

Su, C.-J. and Tassiulas, L., "Broadcast scheduling for information distribution," Proc. IEEE INFOCOM, v1, pp. 109-117, 1997.

Digital Library

[28]

Tsibonis, V. and Geogiadis, L., "Optimal downlink scheduling policies for slotted wireless time-varying channels," IEEE Trans. Wireless Comm., v4, pp. 1808-1817, 2005.

Digital Library

[29]

van Mieghem, J. A., "Dynamic scheduling with convex delay costs: The generalized c | μ rule," Ann. Appl. Probab., v5, pp. 809-833, 1995.

[30]

van Ryzin, G. J. and Mahajan, S., "On the relationship between inventory costs and variety benefits in retail assortments," Management Sci., v45, pp. 1496-1509, 1999.

Digital Library

[31]

Yunes, T. H., Napolitano, D., Scheller-Wolf, A. and Tayur, S., "Building efficient product portfolios at John Deere and Company," Oper. Res., v55, pp. 615-629, 2007.

Digital Library

Cited By

Chen XMa WSimchi-Levi DXin L(2024)Assortment Planning for Recommendations at Checkout Under Inventory ConstraintsMathematics of Operations Research10.1287/moor.2023.135749:1(297-325)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1287/moor.2023.1357
Goyal VUdwani R(2023)Online Matching with Stochastic RewardsOperations Research10.1287/opre.2022.234571:2(563-580)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1287/opre.2022.2345
Aouad ASaban D(2023)Online Assortment Optimization for Two-Sided Matching PlatformsManagement Science10.1287/mnsc.2022.446469:4(2069-2087)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1287/mnsc.2022.4464
Show More Cited By

Stochastic Depletion Problems: Effective Myopic Policies for a Class of Dynamic Optimization Problems
1. Applied computing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Conditions for the existence of decision horizons for discounted problems in a stochastic environment: A note

In this note, we extend the sufficiency conditions obtained by Bean and Smith for the existence of decision and forecast horizons in discounted deterministic problems to a stochastic environment. Also developed are some examples for illustration of the ...
Infinite Horizon Production Scheduling in Time-Varying Systems Under Stochastic Demand

We consider infinite horizon production scheduling under stochastic demand. All problem data are allowed to vary across periods, including demand distributions, costs, and revenues. A forecast horizon, when it exists, is a finite problem horizon with ...
Stochastic optimal control for small noise intensities: the discrete-time case

This paper deals with Markov Decision Processes (MDPs) on Borel spaces with an infinite horizon and a discounted total cost. It will be considered a stochastic optimal control problem which arises by perturbing the transition law of a deterministic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 34, Issue 2

May 2009

256 pages

ISSN:0364-765X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 May 2009

Received: 17 January 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen XMa WSimchi-Levi DXin L(2024)Assortment Planning for Recommendations at Checkout Under Inventory ConstraintsMathematics of Operations Research10.1287/moor.2023.135749:1(297-325)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1287/moor.2023.1357
Goyal VUdwani R(2023)Online Matching with Stochastic RewardsOperations Research10.1287/opre.2022.234571:2(563-580)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1287/opre.2022.2345
Aouad ASaban D(2023)Online Assortment Optimization for Two-Sided Matching PlatformsManagement Science10.1287/mnsc.2022.446469:4(2069-2087)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1287/mnsc.2022.4464
Gong XGoyal VIyengar GSimchi-Levi DUdwani RWang S(2022)Online Assortment Optimization with Reusable ResourcesManagement Science10.1287/mnsc.2021.413468:7(4772-4785)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1287/mnsc.2021.4134
Ma WSimchi-Levi D(2020)Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive RatiosOperations Research10.1287/opre.2019.195768:6(1787-1803)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1287/opre.2019.1957
Ma YRusmevichientong PSumida MTopaloglu H(2020)An Approximation Algorithm for Network Revenue Management Under Nonstationary ArrivalsOperations Research10.1287/opre.2019.193168:3(834-855)Online publication date: 28-Apr-2020
https://dl.acm.org/doi/10.1287/opre.2019.1931
Liu Nvan de Ven PZhang B(2019)Managing Appointment Booking Under Customer ChoicesManagement Science10.1287/mnsc.2018.315065:9(4280-4298)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1287/mnsc.2018.3150
Kim M(2016)Robust Control of Partially Observable Failing SystemsOperations Research10.1287/opre.2016.149564:4(999-1014)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1287/opre.2016.1495
Hellerstein LKletenik DLin P(2015)Discrete Stochastic Submodular MaximizationProceedings of the 9th International Conference on Algorithms and Complexity - Volume 907910.1007/978-3-319-18173-8_17(235-248)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1007/978-3-319-18173-8_17
Arlotto AGans NSteele J(2014)Markov Decision Problems Where Means Bound VariancesOperations Research10.5555/2773183.277319462:4(864-875)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.5555/2773183.2773194
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents