Semidefinite Programming and Approximation Algorithms

半定规划和近似算法

• 批准号: 9908077
• 负责人: Yinyu Ye
• 金额: $ 23.62万
• 依托单位: University of Iowa
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-09-01 至 2002-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9908077&HistoricalAwards=false
• 关键词: Semidefinite; Programming; Approximation; Algorithms

This grant provides funding for the development, analysis, and implementation of semidefinite programming approximation algorithms for solving large-scale combinatorial, discrete, and global optimization problems that arise in production management, manufacture engineering, and network planning. In solving many optimization problems, it is impossible or too costly to obtain a 100 percent optimal solution. However, approximation algorithms can, cost-effectively, deliver a sub-optimal solution with a quality guarantee, say at least 87 percent optimal, which is satisfactory in practice. The semidefinite programming algorithm is a newly developed algorithm for approximating some difficult problems with the best quality guarantees to date. This project is to develop semidefinite programming algorithms for solving a wider class of hard problems with an even better guarantee, and to implement the algorithms in a robust computer code. We then validate the code by solving the network and circuit bisection problem frequently used in the chip design industry, and will test the code on a set of bench-mark problems collected from the industry. If successful, the project would result in one of the most complete and powerful solvers for approximating hard optimization problems with wide real-world applications. It will strengthen and improve theoreticalresults and practical performance of existing approximation algorithms, and will lead to the development of new efficient methods for a variety of discrete optimization problems. Progress in the area of developing efficient algorithms for solving large-scale combinatorial problems is of great importance in improving the efficiency of manufacturing systems, communication networks, aircraft routing, multiple-flow operations,and resources planning. The underlying theory of the project would also be valuable to education and basic scientific research.

这笔资金用于开发、分析和实施半定规划近似算法，用于解决生产管理、制造工程和网络计划中出现的大规模组合、离散和全局优化问题。在解决许多优化问题时，要获得100%的最优解是不可能的，或者代价太高。然而，近似算法可以经济高效地提供次优解决方案，并保证质量，比如说至少87%是最优的，这在实践中是令人满意的。半定规划算法是一种新发展起来的以最好的质量保证逼近某些困难问题的算法。这个项目是开发半定规划算法来解决更广泛类别的困难问题，并以更好的保证，并在健壮的计算机代码中实现这些算法。然后，我们通过解决芯片设计行业中经常使用的网络和电路二等分问题来验证代码，并将代码在从行业收集的一组基准问题上进行测试。如果成功，该项目将产生最完整和最强大的解算器之一，用于近似具有广泛现实应用的困难优化问题。这将加强和改进现有近似算法的理论结果和实际性能，并将导致各种离散优化问题的新的有效方法的发展。在开发解决大规模组合问题的高效算法方面的进展对于提高制造系统、通信网络、飞机路线、多流作业和资源规划的效率具有重要意义。该项目的基本理论对教育和基础科学研究也有价值。