Semidefinite Programming and 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.