Multigrid methods in network optimization : overview and appraisal

Download
Author
Nieto, Javier
Date
1994-03Advisor
Henson, V. Emden
Bradley, Gordon H.
Rasmussen, Craig W.
Metadata
Show full item recordAbstract
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 physics are beginning to appear. This thesis analyzes the application of multigrid methodology to optimization problems. The work is centered on networks. Transportation problems are chosen frequently as reference because they have been the object of some multigrid research. The goal is to establish a basis for development of multigrid-based algorithms. Optimality conditions in linear programming and networks are reviewed, and a compilation of various multilevel approaches in optimization is presented. Emphasis is on the recent scaling techniques; they add some special insights into solving large network problems efficiently using progressive level of detail. An analysis of the difficulties that these problems present to the multigrid approach reveals that perhaps some abstraction is appropriate when interpreting multigrid components applied to optimization problems (in particular, the concept of grid itself). The idea of implicit ordering is developed and associated with the effectiveness of the multigrid method. These concepts are applied to identify problems that can be solved using multigrid. Finally, suggestions for the development of future multigrid-based algorithms are provided
Collections
Related items
Showing items related by title, author, creator and subject.
-
A multilevel approach to minimal cost network flows
Cavanaugh, Kevin J. (Monterey, California. Naval Postgraduate School, 1992-09);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 ... -
Multigrid approach to solving the long transportation problem on a regular grid in cost space
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 ... -
Multicriteria analysis tools in real-life problems
Statnikov, R; Bordetsky, A.; Statnikov, A.; Yanushkevich, I. (Elsevier, 2006);Applied optimization problems such as design, identification, design of controlled systems, operational development of prototypes, analysis of large-scale systems, and forecasting from observational data are multicriteria ...