Back to search

Monterey, California. Naval Postgraduate School

A multilevel approach to minimal cost network flows

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
M.S. in Operations Analysis
Level thesis:degree_level
Masters
Discipline thesis:degree_discipline
Operation Research
Department dc:contributor.department
Department of Operations Research
Grantor dc:publisher
Monterey, California. Naval Postgraduate School
Year dc:date.issued
1992

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cavanaugh, Kevin J.
Advisors dc:contributor.advisor
  • Henson, Van Emden
  • Rosenthal, Richard E.

Rights

dc:rights
Statement dc:rights
  • This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
  • Approved for public release; distribution is unlimited.

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10945/23972

Chain of custody

source
Harvested from
Naval Postgraduate School
Base URL
calhoun.nps.edu/server/oai/request
Last updated
2026-11-20
Source record
OAI-PMH GetRecord
related terms
citation

Cavanaugh, Kevin J.. A multilevel approach to minimal cost network flows. Masters thesis, Monterey, California. Naval Postgraduate School, 1992. https://hdl.handle.net/10945/23972