A Multilevel Approach to Minimum Cost Network Flows

Abstract

Multigrid/multilevel techniques were originally developed for numerically solving partial differential equations. This thesis explores the application of 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. Directions for future work include investigation of graph theoretic aspects of the problems, 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.... Multigrid, Multilevel, Optimization, Networks, Transportation problem, Aggregation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1992
Accession Number
ADA264008

Entities

People

  • Kevin J. Cavanaugh

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Coast Guard
  • Computations
  • Computer Programs
  • Difference Equations
  • Differential Equations
  • Frequency
  • Linear Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Partial Differential Equations
  • Schools
  • Security
  • Simplex Method
  • United States

Readers

  • Computational Modeling and Simulation
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Systems Analysis and Design

Technology Areas

  • Space