Rapidly Solving an Online Sequence of Maximum Flow Problems

We investigate how to rapidly solve an online sequence of maximum flow problems. Sequences of maximum flow problems arise in a diverse collection of settings, including stochastic network programming and real-time scheduling of jobs on a two-processor computer. In this paper, we formulate solving an online sequence of maximum flow problems as the Maximum Flow Reoptimization Problem, introduce a maximum flow algorithm designed for ``warm starts,'' and present computational results.


Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, March, 2008.