A dynamic network flow problem with uncertain arc capacities: Formulation and problem structure
成果类型：
Article
署名作者：
Glockner, GD; Nemhauser, GL
署名单位：
University System of Georgia; Georgia Institute of Technology
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.2.233.12384
发表日期：
2000
页码：
233-242
关键词：
摘要：
We consider a dynamic network flow problem where the are capacities are random variables. This gives a multistage stochastic linear program. We describe the randomness using a multi-scenario approach. Because of the multilayered structure, there are several ways to decompose the linear program. We classify different decomposition schemes, and we develop a scheme called compath decomposition, which is derived from path decomposition for network flows. We give a polynomial-time algorithm to find a cheapest compath that can solve the subproblems resulting from compath decomposition. Finally, compath decomposition is extended to multicommodity flow problems.