Minimum cardinality non-anticipativity constraint sets for multistage stochastic programming

作     者：Boland, Natashia Dumitrescu, Irina Froyland, Gary Kalinowski, Thomas 

作者机构：Univ Newcastle Univ Dr Callaghan NSW 2308 Australia IBM Res Australia Carlton Vic Australia Univ Melbourne Melbourne Vic Australia Univ New S Wales Sydney NSW Australia Univ Newcastle Callaghan NSW 2308 Australia Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA 

出 版 物：《MATHEMATICAL PROGRAMMING》 (数学规划)

年 卷 期：2016年第157卷第1期

页      面：69-93页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0835[工学-软件工程] 0701[理学-数学] 

基　　金：Australian Research Council [LP0561744] Australian Research Council [LP0561744] Funding Source: Australian Research Council 

主　　题：Stochastic programming Endogeneous uncertainty Multistage stochastic programming 

摘      要：We consider multistage stochastic programs, in which decisions can adapt over time, (i.e., at each stage), in response to observation of one or more random variables (uncertain parameters). The case that the time at which each observation occurs is decision-dependent, known as stochastic programming with endogeneous observation of uncertainty, presents particular challenges in handling non-anticipativity. Although such stochastic programs can be tackled by using binary variables to model the time at which each endogenous uncertain parameter is observed, the consequent conditional non-anticipativity constraints form a very large class, with cardinality in the order of the square of the number of scenarios. However, depending on the properties of the set of scenarios considered, only very few of these constraints may be required for validity of the model. Here we characterize minimal sufficient sets of non-anticipativity constraints, and prove that their matroid structure enables sets of minimum cardinality to be found efficiently, under general conditions on the structure of the scenario set.