Network Optimization Algorithms

网络优化算法

• 批准号: 9108058
• 负责人: Dimitri Bertsekas
• 金额: $ 7.47万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-06-15 至 1994-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9108058&HistoricalAwards=false
• 关键词: 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.

工程和资源管理中的许多操作都会遇到优化问题，即优化选择影响生产率指数的几个因素的数学问题。这些都是在过去三十年中被广泛研究的具有相当大计算难度的问题。这个项目关注几个这样的具有网络结构的问题，它涉及一类最近提出的方法，称为拍卖和松弛算法。所要解决的问题从经典的指派、运输、转运和最短路径问题到一些新型的多指派问题。这些问题在实践中经常出现，而且规模往往很大。改进解决这些问题的方法将产生重大的实际影响。这项研究将旨在了解现有网络算法的性能，并将基于拍卖和关系思想开发性能更高的算法。