Network Optimization Algorithms

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

Many operations in engineering and resource management encounter optimization problems, that is, mathematical problems of choosing optimally several factors that affect a productivity index. These are problems of considerable computational difficulty that have been extensively investigated in the last three decades. This project focuses on several such problems that have a network structure, and it relates to a class of recently proposed methods called auction and relaxation algorithms. The problems to be addressed range from the classical assignment, transportation, transshipment, and shortest path problems to some new types of multiassignment problems. These problems arise very often in practice and their size is often very large. Methodological improvements for the solution of these problems will have significant practical impact. The investigation will aim at the understanding of the performance of existing network algorithms and will develop algorithms with improved performance based on auction and relation ideas.