IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v87y2024i2d10.1007_s10589-023-00529-5.html
   My bibliography  Save this article

Distribution-free algorithms for predictive stochastic programming in the presence of streaming data

Author

Listed:
  • Shuotao Diao

    (University of Southern California)

  • Suvrajeet Sen

    (University of Southern California)

Abstract

This paper studies a fusion of concepts from stochastic programming and non-parametric statistical learning in which data is available in the form of covariates interpreted as predictors and responses. Such models are designed to impart greater agility, allowing decisions under uncertainty to adapt to the knowledge of predictors (leading indicators). This paper studies two classes of methods for such joint prediction-optimization models. One of the methods may be classified as a first-order method, whereas the other studies piecewise linear approximations. Both of these methods are based on coupling non-parametric estimation for predictive purposes, and optimization for decision-making within one unified framework. In addition, our study incorporates several non-parametric estimation schemes, including k nearest neighbors (kNN) and other standard kernel estimators. Our computational results demonstrate that the new algorithms proposed in this paper outperform traditional approaches which were not designed for streaming data applications requiring simultaneous estimation and optimization as important design features for such algorithms. For instance, coupling kNN with Stochastic Decomposition (SD) turns out to be over 40 times faster than an online version of Benders Decomposition while finding decisions of similar quality. Such computational results motivate a paradigm shift in optimization algorithms that are intended for modern streaming applications.

Suggested Citation

  • Shuotao Diao & Suvrajeet Sen, 2024. "Distribution-free algorithms for predictive stochastic programming in the presence of streaming data," Computational Optimization and Applications, Springer, vol. 87(2), pages 355-395, March.
    • Handle: RePEc:spr:coopap:v:87:y:2024:i:2:d:10.1007_s10589-023-00529-5
    DOI: 10.1007/s10589-023-00529-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-023-00529-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-023-00529-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yehuda Bassok & Ravi Anupindi & Ram Akella, 1999. "Single-Period Multiproduct Inventory Models with Substitution," Operations Research, INFORMS, vol. 47(4), pages 632-642, August.
    2. Yichun Hu & Nathan Kallus & Xiaojie Mao, 2022. "Fast Rates for Contextual Linear Optimization," Management Science, INFORMS, vol. 68(6), pages 4236-4245, June.
    3. Richard Blundell & Alan Duncan, 1998. "Kernel Regression in Empirical Microeconomics," Journal of Human Resources, University of Wisconsin Press, vol. 33(1), pages 62-87.
    4. Z. I. Botev, 2017. "The normal law under linear restrictions: simulation and estimation via minimax tilting," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(1), pages 125-148, January.
    5. Suvrajeet Sen & Yifan Liu, 2016. "Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction," Operations Research, INFORMS, vol. 64(6), pages 1422-1437, December.
    6. Julia L. Higle & Suvrajeet Sen, 1991. "Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse," Mathematics of Operations Research, INFORMS, vol. 16(3), pages 650-669, August.
    7. Yunxiao Deng & Suvrajeet Sen, 2022. "Predictive stochastic programming," Computational Management Science, Springer, vol. 19(1), pages 65-98, January.
    8. Walk, Harro, 2008. "A universal strong law of large numbers for conditional expectations via nearest neighbors," Journal of Multivariate Analysis, Elsevier, vol. 99(6), pages 1035-1050, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jiajun Xu & Suvrajeet Sen, 2024. "Ensemble Variance Reduction Methods for Stochastic Mixed-Integer Programming and their Application to the Stochastic Facility Location Problem," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 587-599, March.
    2. Ward Romeijnders & David P. Morton & Maarten H. van der Vlerk, 2017. "Assessing the Quality of Convex Approximations for Two-Stage Totally Unimodular Integer Recourse Models," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 211-231, May.
    3. Atakan, Semih & Gangammanavar, Harsha & Sen, Suvrajeet, 2022. "Towards a sustainable power grid: Stochastic hierarchical planning for high renewable integration," European Journal of Operational Research, Elsevier, vol. 302(1), pages 381-391.
    4. Sadana, Utsav & Chenreddy, Abhilash & Delage, Erick & Forel, Alexandre & Frejinger, Emma & Vidal, Thibaut, 2025. "A survey of contextual optimization methods for decision-making under uncertainty," European Journal of Operational Research, Elsevier, vol. 320(2), pages 271-289.
    5. Harsha Gangammanavar & Yifan Liu & Suvrajeet Sen, 2021. "Stochastic Decomposition for Two-Stage Stochastic Linear Programs with Random Cost Coefficients," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 51-71, January.
    6. Suvrajeet Sen & Yifan Liu, 2016. "Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction," Operations Research, INFORMS, vol. 64(6), pages 1422-1437, December.
    7. Yunxiao Deng & Suvrajeet Sen, 2022. "Predictive stochastic programming," Computational Management Science, Springer, vol. 19(1), pages 65-98, January.
    8. Postek, Krzysztof & Romeijnders, Ward & den Hertog, Dick & van der Vlerk, Maarten H., 2019. "An approximation framework for two-stage ambiguous stochastic integer programs under mean-MAD information," European Journal of Operational Research, Elsevier, vol. 274(2), pages 432-444.
    9. Jangho Park & Rebecca Stockbridge & Güzin Bayraksan, 2021. "Variance reduction for sequential sampling in stochastic programming," Annals of Operations Research, Springer, vol. 300(1), pages 171-204, May.
    10. Corak, Miles & Lauzon, Darren, 2009. "Differences in the distribution of high school achievement: The role of class-size and time-in-term," Economics of Education Review, Elsevier, vol. 28(2), pages 189-198, April.
    11. M. Jenabi & S. M. T. Fatemi Ghomi & S. A. Torabi & Moeen Sammak Jalali, 2022. "An accelerated Benders decomposition algorithm for stochastic power system expansion planning using sample average approximation," OPSEARCH, Springer;Operational Research Society of India, vol. 59(4), pages 1304-1336, December.
    12. Ichimura, Hidehiko & Todd, Petra E., 2007. "Implementing Nonparametric and Semiparametric Estimators," Handbook of Econometrics, in: J.J. Heckman & E.E. Leamer (ed.), Handbook of Econometrics, edition 1, volume 6, chapter 74, Elsevier.
    13. Jan A. Van Mieghem & Nils Rudi, 2002. "Newsvendor Networks: Inventory Management and Capacity Investment with Discretionary Activities," Manufacturing & Service Operations Management, INFORMS, vol. 4(4), pages 313-335, August.
    14. BERTINELLI, Luisito & STROBL, Eric, 2003. "Urbanization, urban concentration and economic growth in developing countries," LIDAM Discussion Papers CORE 2003076, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. Laura Liu & Hyungsik Roger Moon & Frank Schorfheide, 2023. "Forecasting with a panel Tobit model," Quantitative Economics, Econometric Society, vol. 14(1), pages 117-159, January.
    16. Barrios, Salvador & Strobl, Eric, 2009. "The dynamics of regional inequalities," Regional Science and Urban Economics, Elsevier, vol. 39(5), pages 575-591, September.
    17. Inderfurth, Karl, 2004. "Optimal policies in hybrid manufacturing/remanufacturing systems with product substitution," International Journal of Production Economics, Elsevier, vol. 90(3), pages 325-343, August.
    18. David S. Lee & Thomas Lemieux, 2009. "Regression Discontinuity Designs In Economics," Working Papers 1118, Princeton University, Department of Economics, Industrial Relations Section..
    19. D. Kuhn, 2009. "Convergent Bounds for Stochastic Programs with Expected Value Constraints," Journal of Optimization Theory and Applications, Springer, vol. 141(3), pages 597-618, June.
    20. Zhang, Jie & Xie, Weijun & Sarin, Subhash C., 2021. "Robust multi-product newsvendor model with uncertain demand and substitution," European Journal of Operational Research, Elsevier, vol. 293(1), pages 190-202.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:87:y:2024:i:2:d:10.1007_s10589-023-00529-5. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.