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

Gregory D. Glockner, George L. Nemhauser

Operations Research · 2000 · Volume 48 · Issue 2

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

Enable JavaScript for citation tools and additional paper interactions.