IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v87y2018i1d10.1007_s00186-017-0600-6.html
   My bibliography  Save this article

Reduction of nonanticipativity constraints in multistage stochastic programming problems with endogenous and exogenous uncertainty

Author

Listed:
  • F. Hooshmand

    (Amirkabir University of Technology)

  • S. A. MirHassani

    (Amirkabir University of Technology)

Abstract

Multistage stochastic programming (SP) with both endogenous and exogenous uncertainties is a novel problem in which some uncertain parameters are decision-dependent and others are independent of decisions. The main difficulty of this problem is that nonanticipativity constraints (NACs) make up a significantly large constraint set, growing very fast with the number of scenarios and leading to an intractable model. Usually, a lot of these constraints are redundant and hence, identification and elimination of redundant NACs can cause a significant reduction in the problem size. Recently, a polynomial time algorithm has been proposed in the literature which is able to identify all redundant NACs in an SP problem with only endogenous uncertainty. In this paper, however, we extend the algorithm proposed in the literature and present a new method which is able to make the upper most possible reduction in the number of NACs in any SP with both exogenous and endogenous uncertain parameters. Proving the validity of this method is another innovation of this study. Computational results confirm that the proposed approach can significantly reduce the problem size within a reasonable computation time.

Suggested Citation

  • F. Hooshmand & S. A. MirHassani, 2018. "Reduction of nonanticipativity constraints in multistage stochastic programming problems with endogenous and exogenous uncertainty," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 87(1), pages 1-18, February.
    • Handle: RePEc:spr:mathme:v:87:y:2018:i:1:d:10.1007_s00186-017-0600-6
    DOI: 10.1007/s00186-017-0600-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00186-017-0600-6
    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/s00186-017-0600-6?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. Bora Tarhan & Ignacio Grossmann & Vikas Goel, 2013. "Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution," Annals of Operations Research, Springer, vol. 203(1), pages 141-166, March.
    2. F. Hooshmand Khaligh & S.A. MirHassani, 2016. "A mathematical model for vehicle routing problem under endogenous uncertainty," International Journal of Production Research, Taylor & Francis Journals, vol. 54(2), pages 579-590, January.
    3. Solak, Senay & Clarke, John-Paul B. & Johnson, Ellis L. & Barnes, Earl R., 2010. "Optimization of R&D project portfolios under endogenous uncertainty," European Journal of Operational Research, Elsevier, vol. 207(1), pages 420-433, November.
    4. Colvin, Matthew & Maravelias, Christos T., 2010. "Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming," European Journal of Operational Research, Elsevier, vol. 203(1), pages 205-215, May.
    5. Tore Jonsbråten & Roger Wets & David Woodruff, 1998. "A class of stochastic programs withdecision dependent random elements," Annals of Operations Research, Springer, vol. 82(0), pages 83-106, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Giovanni Pantuso, 2021. "A node formulation for multistage stochastic programs with endogenous uncertainty," Computational Management Science, Springer, vol. 18(3), pages 325-354, July.
    2. Escudero, Laureano F. & Garín, M. Araceli & Monge, Juan F. & Unzueta, Aitziber, 2020. "Some matheuristic algorithms for multistage stochastic optimization models with endogenous uncertainty and risk management," European Journal of Operational Research, Elsevier, vol. 285(3), pages 988-1001.
    3. Saeid Nasrollahi & Hasan Hosseini-Nasab & Mohammad Bagher Fakhrzad & Mahboobeh Honarvar, 2023. "A multi-stage stochastic model for designing a linked cross-docking distribution network with heterogeneous trucks," Operational Research, Springer, vol. 23(1), pages 1-41, March.

    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. Maier, Sebastian & Pflug, Georg C. & Polak, John W., 2020. "Valuing portfolios of interdependent real options under exogenous and endogenous uncertainties," European Journal of Operational Research, Elsevier, vol. 285(1), pages 133-147.
    2. Feng, Wei & Feng, Yiping & Zhang, Qi, 2021. "Multistage robust mixed-integer optimization under endogenous uncertainty," European Journal of Operational Research, Elsevier, vol. 294(2), pages 460-475.
    3. Giovanni Pantuso, 2021. "A node formulation for multistage stochastic programs with endogenous uncertainty," Computational Management Science, Springer, vol. 18(3), pages 325-354, July.
    4. Mahmutoğulları, Özlem & Yaman, Hande, 2023. "Robust alternative fuel refueling station location problem with routing under decision-dependent flow uncertainty," European Journal of Operational Research, Elsevier, vol. 306(1), pages 173-188.
    5. Sha, Yue & Zhang, Junlong & Cao, Hui, 2021. "Multistage stochastic programming approach for joint optimization of job scheduling and material ordering under endogenous uncertainties," European Journal of Operational Research, Elsevier, vol. 290(3), pages 886-900.
    6. Tahir Ekin & Nicholas G. Polson & Refik Soyer, 2017. "Augmented nested sampling for stochastic programs with recourse and endogenous uncertainty," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(8), pages 613-627, December.
    7. Ekin, Tahir, 2018. "Integrated maintenance and production planning with endogenous uncertain yield," Reliability Engineering and System Safety, Elsevier, vol. 179(C), pages 52-61.
    8. Colvin, Matthew & Maravelias, Christos T., 2011. "R&D pipeline management: Task interdependencies and risk management," European Journal of Operational Research, Elsevier, vol. 215(3), pages 616-628, December.
    9. Abdoli, B. & Hooshmand, F. & MirHassani, S.A., 2023. "A novel stochastic programming model under endogenous uncertainty for the CCS-EOR planning problem," Applied Energy, Elsevier, vol. 338(C).
    10. Eyyüb Y. Kıbış & İ. Esra Büyüktahtakın & Robert G. Haight & Najmaddin Akhundov & Kathleen Knight & Charles E. Flower, 2021. "A Multistage Stochastic Programming Approach to the Optimal Surveillance and Control of the Emerald Ash Borer in Cities," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 808-834, May.
    11. Salo, Ahti & Andelmin, Juho & Oliveira, Fabricio, 2022. "Decision programming for mixed-integer multi-stage optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 299(2), pages 550-565.
    12. Nilay Noyan & Gábor Rudolf & Miguel Lejeune, 2022. "Distributionally Robust Optimization Under a Decision-Dependent Ambiguity Set with Applications to Machine Scheduling and Humanitarian Logistics," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 729-751, March.
    13. Kavitha G. Menon & Ricardo Fukasawa & Luis A. Ricardez-Sandoval, 2021. "A novel stochastic programming approach for scheduling of batch processes with decision dependent time of uncertainty realization," Annals of Operations Research, Springer, vol. 305(1), pages 163-190, October.
    14. Lars Hellemo & Paul I. Barton & Asgeir Tomasgard, 2018. "Decision-dependent probabilities in stochastic programs with recourse," Computational Management Science, Springer, vol. 15(3), pages 369-395, October.
    15. Majid Taghavi & Kai Huang, 2020. "A Lagrangian relaxation approach for stochastic network capacity expansion with budget constraints," Annals of Operations Research, Springer, vol. 284(2), pages 605-621, January.
    16. Solak, Senay & Clarke, John-Paul B. & Johnson, Ellis L. & Barnes, Earl R., 2010. "Optimization of R&D project portfolios under endogenous uncertainty," European Journal of Operational Research, Elsevier, vol. 207(1), pages 420-433, November.
    17. Doan, Xuan Vinh, 2022. "Distributionally robust optimization under endogenous uncertainty with an application in retrofitting planning," European Journal of Operational Research, Elsevier, vol. 300(1), pages 73-84.
    18. Kopa, Miloš & Rusý, Tomáš, 2023. "Robustness of stochastic programs with endogenous randomness via contamination," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1259-1272.
    19. Tahir Ekin & Stephen Walker & Paul Damien, 2023. "Augmented simulation methods for discrete stochastic optimization with recourse," Annals of Operations Research, Springer, vol. 320(2), pages 771-793, January.
    20. Liesiö, Juuso & Kee, Taeyoung & Malo, Pekka, 2024. "Modeling project interactions in multiattribute portfolio decision analysis: Axiomatic foundations and practical implications," European Journal of Operational Research, Elsevier, vol. 316(3), pages 988-1000.

    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:mathme:v:87:y:2018:i:1:d:10.1007_s00186-017-0600-6. 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.