芯片及网络设计中的图优化问题研究

Chip design and related network science issues are very attractive areas of application for graph theory and combinatorial optimization. In fact, all the classical combinatorial optimization problems and some newly proposed problems are all sub-problems. Due to the rapid development of technologies and important theoretical research, it has become increasingly meaningful to apply the combinatorial optimization randomized algorithms in graph optimization to VLSI in the past few decades. It is hard to imagine how importnoant mathematics is, especially the combinatorial optimization problems over graph apply to almost all parts of VLSI and related network design. The project research has a background of the times, and has been rapid development in recent decades. Due to the increasing integration of the chip, which also means that in the process of chip design we need to deal with the increasing amount of data, how to deal with massive data is a very challenging issue in information science that requires multidisciplinary techniques such as nonlinear combinatorial optimization and computational mathematics. We have selected some hot and difficult issues in the field at present which have important theoretical and practical values ​​for further research. We will use mathematical methods to investigate some graph problems of optimization related to network design in chip design process. We hope that the research on each topic will get substantive development which can cultivate a higher level of reserve youth power for our country in this field and produce practical influence and utility in the application field.

芯片设计和相关网络科学问题是图论与组合优化非常引人入胜的应用领域。实际上所有经典的图上组合优化问题和一些新提出的问题，都是它的子问题。由于高速发展的技术和重要理论的不断突破，在过去的几十年间，将图优化中的组合优化随机算法运用到VLSI已经变得越来越有意义。很难想象数学是多么的重要，特别是图上组合优化问题适用于VLSI及相关网络设计中的大部分问题。项目研究的问题具有时代背景，由于芯片集成度越来越大，这也意味着在设计芯片的过程中需要处理的数据量也逐渐增加，如何处理海量的数据也是信息科学中具有挑战性的问题，在本课题研究中特别需要结合非线性组合优化和计算数学等多学科的技术。我们选取了当前该领域的一些热点和难点问题，围绕芯片设计流程中与网络设计相关的若干图优化问题运用数学手段深入研究，希望在理论和方法上取得较大突破，为我国在此领域的发展培养更多高水平的年轻研究人才，并在应用领域产生实际的影响和效用。

在信息网络时代与信息网络相关的超大规模图优化问题不断涌现，迄今为止，随着算法、算力的非连续创新突破，以及5G、云计算等基础设施的迅猛发展与逐步完善，信息网络技术正逐渐成为新一代通用技术，是推动经济社会发展的新引擎。与集成电路设计和网络设计相关的图优化问题需要用到图论与组合优化、计算数学等多学科交叉方法。近年来，与集成电路设计和网络设计相关的研究领域不再只是计算机专业的研究方向，实际上所有经典组合优化问题和一些新提出的图优化问题，都是它们的子问题，特别是图优化方法也在这个方面得到了广泛的应用。课题组在已取得的研究成果中充分利用了图论算法和数学优化以及基于线性规划和半正定规划松弛等随机舍入方法深入研究了这些问题的结构特性以及在求解近似算法和图算法方面获得了重要进展，文章发表在IEEE Transactions on Information Theory、Journal of Graph Theory、Journal of Global Optimization、 Optimization Methods and Software、Theoretical Computer Science、Journal of Combinatorial Optimization、Discrete Applied Mathematics、Discrete Mathematics、Tsinghua Science & Technology、Computers and Electrical Engineering等一系列重要SCI期刊，并受德国波恩大学离散数学研究所芯片设计专家 Stefan Hougardy 教授和Jens Vygen教授委托翻译出版《算法数学》学术著作一部，该书已在 Springer 出版社短期内出版了德、英两个版本，中译版在高等教育出版社的大力支持下于2021年8月出版，研究团队目前申请软件著作权一项，正在申请若干发明专利，研究实质进展具有重要的理论意义和应用价值。