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.
Citation
Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, March, 2008.