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. 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.
    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. Yunxiao Deng & Suvrajeet Sen, 2022. "Predictive stochastic programming," Computational Management Science, Springer, vol. 19(1), pages 65-98, January.
    7. 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.
    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. 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.
    11. 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.
    12. 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.
    13. Veiga, Sébastien Da & Marrel, Amandine, 2020. "Gaussian process regression with linear inequality constraints," Reliability Engineering and System Safety, Elsevier, vol. 195(C).
    14. Kim, Nayeon & Montreuil, Benoit & Klibi, Walid & Zied Babai, M., 2023. "Network inventory deployment for responsive fulfillment," International Journal of Production Economics, Elsevier, vol. 255(C).
    15. Ozen, U. & Slikker, M. & Norde, H.W., 2007. "A General Framework for Cooperation under Uncertainty," Discussion Paper 2007-57, Tilburg University, Center for Economic Research.
    16. Lingxiu Dong & Panos Kouvelis & Zhongjun Tian, 2009. "Dynamic Pricing and Inventory Control of Substitute Products," Manufacturing & Service Operations Management, INFORMS, vol. 11(2), pages 317-339, December.
    17. Ketabchi, Saeed & Behboodi-Kahoo, Malihe, 2015. "Augmented Lagrangian method within L-shaped method for stochastic linear programs," Applied Mathematics and Computation, Elsevier, vol. 266(C), pages 12-20.
    18. Riis, Morten & Andersen, Kim Allan, 2005. "Applying the minimax criterion in stochastic recourse programs," European Journal of Operational Research, Elsevier, vol. 165(3), pages 569-584, September.
    19. Xiaotie Chen & David L. Woodruff, 2024. "Distributions and bootstrap for data-based stochastic programming," Computational Management Science, Springer, vol. 21(1), pages 1-21, June.
    20. 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.

    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.