TY - JOUR
T1 - A branch and cut framework for multi-stage stochastic programming problems under endogenous uncertainty
AU - Colvin, Matthew
AU - Maravelias, Christos T.
N1 - Funding Information:
The authors of this paper would like to acknowledge support from the National Science Foundation under Grant CTS-0547443.
PY - 2009
Y1 - 2009
N2 - To ensure that decisions in multi-stage stochastic programming (MSSP) formulations do not anticipate future outcomes, it is necessary to introduce nonanticipativity constraints (NACs). In the case of endogenous uncertainty, NACs grow very quickly making all but the smailest multi-stage stochastic programming models computationaily intractable. To address this challenge, we first present a number of theoretical results that allow us to formulate substantially smaller and tighter MSSP models. Second, we discuss a branch and cut algorithm where necessary inequality NACs are removed from the starting formulation and added only if they are violated. Our theoretical results coupled with the proposed algorithm allow us to generate and solve problems that were previously intractable. The methods were applied to the resource-constrained scheduling of ciinical triais in the pharmaceutical research and deveiopment pipeline.
AB - To ensure that decisions in multi-stage stochastic programming (MSSP) formulations do not anticipate future outcomes, it is necessary to introduce nonanticipativity constraints (NACs). In the case of endogenous uncertainty, NACs grow very quickly making all but the smailest multi-stage stochastic programming models computationaily intractable. To address this challenge, we first present a number of theoretical results that allow us to formulate substantially smaller and tighter MSSP models. Second, we discuss a branch and cut algorithm where necessary inequality NACs are removed from the starting formulation and added only if they are violated. Our theoretical results coupled with the proposed algorithm allow us to generate and solve problems that were previously intractable. The methods were applied to the resource-constrained scheduling of ciinical triais in the pharmaceutical research and deveiopment pipeline.
KW - Branch and cut
KW - Endogenous uncertainty
KW - Stochastic programming
UR - http://www.scopus.com/inward/record.url?scp=77649324830&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77649324830&partnerID=8YFLogxK
U2 - 10.1016/S1570-7946(09)70263-9
DO - 10.1016/S1570-7946(09)70263-9
M3 - Article
AN - SCOPUS:77649324830
SN - 1570-7946
VL - 27
SP - 255
EP - 260
JO - Computer Aided Chemical Engineering
JF - Computer Aided Chemical Engineering
IS - C
ER -