MIMD, SIMD, and Hybrid Parallelism for Network Optimization

点击翻译按钮获取中文摘要

Parallel algorithms for various classes of large-scale network optimization problems will be developed and tested. Research will focus on the following classes of network flow problems: l. Pure single-commodity 2. Generalized (networks with gains and losses) 3. Nonlinear 4. Multicommodity These problem classes span a very broad range of large-scale real-world applications as well as a spectrum of mathematical classes. They also form a natural continuum, since parallel techniques developed for the first two classes of linear networks are often relevant to the latter two classes, in which single-commodity linear networks may arise as subproblems. Thus, there are synergetic relationships between these areas. A goal of the research is to unify and extend earlier results in parallel optimization in order to obtain efficient algorithms that are based on a variety of primal and dual decomposition approaches and suited to implementations on multicomputer as well as multiprocessor architectures. These methods will be tested on large-scale test problems on the parallel systems available locally as well as on other parallel hardware available via Internet.