A multilevel approach to minimal cost network flows
Cavanaugh, Kevin J.
Henson, Van Emden
Rosenthal, Richard E.
MetadataShow full item record
This thesis presents an exploration of the application of multigrid/multilevel techniques to a non-geometric long transportation problem. An introduction to multigrid is given, and specifics of how it is applied to this minimum cost network flow problem are explored. This research shows that multilevel techniques can be applied to network optimization problems. Further, since a previous restriction is removed by transferring the problem from a physical space to a cost space, the techniques can be applied to a broader range of problems. Both a multilevel V-cycle and a Full Multigrid (FMG) algorithm are implemented. Various strategies for restriction and local relaxation are discussed, and comparisons between the methods are made. Experimental results are given. Directions for future work include investigation of graph theoretic aspects of the problem, implementation of a regular grid overlay of the domain, exploration of a fast adaptive composite (FAC) grid algorithm, and development of a full approximation scheme (FAS) algorithm.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Nieto, Javier (Monterey, California. Naval Postgraduate School, 1994-03);Multigrid methods have been traditionally applied to the solution of certain Partial Differential Equations. However, applications in control theory, optimization, pattern recognition, computational tomography and particle ...
Finite volume element (FVE) discretization and multilevel solution of the axisymmetric heat equation Litaker, Eric T. (Monterey, California. Naval Postgraduate School, 1994-12);The axisymmetric heat equation, resulting from a point-source of heat applied to a metal block, is solved numerically; both iterative and multilevel solutions are computed in order to compare the two processes. The continuum ...
Cornett, Annette P. (Monterey, California. Naval Postgraduate School, 1993-06);Multigrid methods were developed to solve partial differential equations. Research has shown that these methods are applicable to a broader range of problems. This thesis investigates the application of multigrid techniques ...