AN ADAPTIVE DISCRETIZATION ALGORITHM FOR A CLASS OF CONTINUOUS NETWORK PROGRAMS

An algorithm is derived for a class of continuous-time minimum-cost network flow problems. The algorithm is based on some recent results in the theory of separated continuous linear programs and works with a sequence of discrete approximations to the continuous-time problem. We prove the convergence of the algorithm and present some numerical results which compare its performance against that of linear network flow algorithms applied to a uniform discrete approximation of the continuous-time problem. (C) 1995 John Wiley and Sons, Inc.