A Dynamic Network Flow Problem with Uncertain arc Capacities: Formulation and Problem Structure

Gregory D. Glockner () and George L. Nemhauser
Additional contact information
Gregory D. Glockner: ILOG, Inc., 1080 Linda Vista Avenue, Mountain View, California 94043
George L. Nemhauser: Logistics Engineering Center, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Operations Research, 2000, vol. 48, issue 2, 233-242

Abstract: We consider a dynamic network flow problem where the arc 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.

Keywords: Networks; graphs; stochastic: dynamic network flow with uncertain arc capabilities (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.2.233.12384 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:2:p:233-242

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().