A graph theoretic approach to non-anticipativity constraint generation in multistage stochastic programs with incomplete scenario sets. (October 2022)

• Record Type: Journal Article
• Authors: Zeng, Zuo; Vinel, Alexander; Christian, Brianna; Shoji, Yasuhiro; Cremaschi, Selen
• Is Part Of: Computers & operations research. Volume 146(2022)
• Publication Date: 2022-10
• Subjects: Stochastic programming -- Multistage stochastic models -- Endogenous uncertainty -- Non-anticipativity constraints; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105886
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Multistage-stochastic programming (MSSP) problems under both endogenous and exogenous uncertainties with gradual realization have been gaining attention in the literature, particularly, in chemical engineering applications. Recently several approaches have been introduced to generate the minimum cardinality non-anticipativity constraint (NAC) set for stochastic programs with various scenario set structures. However, they have been limited to uncertain parameters where the realizations occur instantaneously or the full set of scenarios is required, and may require reformulating the problem. This paper proposes an algorithm for generating a minimum cardinality set of NACs for MSSP problems under both endogenous and exogenous uncertainties with gradual realization without the need for (often non-trivial) reformulations. In addition, a heuristic version of this algorithm, which does not guarantee minimum NAC set, but allows for an efficient decomposable implementation, is developed. A thorough computational study demonstrates the benefit of reducing the NAC set, and compares the case of minimum vs near-minimum NAC sets, which has not been widely studied before. Highlights: Our algorithm works for gradual realization of uncertainty and partial scenario sets. The algorithm reduces the number of non-anticipativity constraints. A heuristic version of the algorithm returns near-minimum NAC set. Reduction of the number of NACs leads to significantly shorter solution times.