Efficient constraint reduction in multistage stochastic programming problems with endogenous uncertainty. (3rd March 2016)

• Record Type: Journal Article
• Authors: Hooshmand, F.; MirHassani, S.A.
• Is Part Of: Optimization methods and software. Volume 31:Number 2(2016)
• Page Start: 359
• Page End: 376
• Publication Date: 2016-03-03
• Subjects: multistage stochastic programming -- endogenous uncertainty -- redundant nonanticipativity constraints -- minimal graph -- exact polynomial time algorithm; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2015.1088850
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : Multistage stochastic programming with endogenous uncertainty is a new topic in which the timing of uncertainty realization is decision-dependent. In this case, the number of nonanticipativity constraints (NACs) increases very quickly with the number of scenarios, making the problem computationally intractable. Fortunately, a large number of NACs are typically redundant and their elimination leads to a considerable reduction in the problem size. Identifying redundant NACs has been addressed in the literature only in the special case where the scenario set is equal to the Cartesian product of all possible outcomes for endogenous parameters; however, this is a scarce condition in practice. In this paper, we consider the general case where the scenario set is an arbitrary set; and two approaches, able to identify all redundant NACs, are proposed. The first approach is by mixed integer programming formulation and the second one is an exact polynomial time algorithm. Proving the fact that the proposed algorithm is able to make the uppermost reduction in the number of NACs is another novelty of this paper. Computational results evaluate the efficiency of the proposed approaches.