离散数学及其应用教育部重点实验室工作总结报告 （2012年2月10日）
实验室名称： 离散数学及其应用教育部重点实验室 主管部门： 福建省教育厅 依托单位： 福州大学
实验室概况: 在迅速发展的计算机科学技术及信息技术等领域，离散数学是重要的基础学科和支撑学科，它的发展和应用是影响一个国家科学技术发展水平的重要因素。以福州大学“离散数学与理论计算机科学研究中心”为依托的离散数学及其应用教育部重点实验室于2007年7月获教育部批准立项建设。目前，实验室共有固定研究人员27人，其中教授16人，副教授4人。实验室由马志明院士担任学术委员会主任，范更华教授担任实验室主任。实验室位于福州大学铜盘校区。2007年11月完成了实验室装修一期工程；2009年3月完成了二期装修工程，达到 “环境优美、设备一流”。按国际研究所标准建设基础设施，为每位研究人员及来访学者提供40平米宽敞办公室及一流科研设备。为每位研究生提供一个工作位及台式电脑。已建成无线网覆盖实验室3000平米的科研、办公场所。重视网络建设，保证网络高速畅通。订购相关专业的国外数据库及原版图书，已基本建成一流的专业图书资料室。
一、实验室现有三个研究方向：图论与组合数学、大规模集成电路设计中的数学方法、优化理论与算法。
二、在本年度，实验室在研科研项目国家973计划课题1项，国家自然科学基金8项，其中重点项目1项，面上项目6项，青年项目1项。国家科技部产学研项目1项，教育部高校博士点专项科研基金联合资助课题1项， 新增国家自然科学基金3项，均为青年项目，分别是：
1.矩阵定性分析中Ray非异及复符号非异矩阵的特征刻画（11101088），刘月。
1 2.图的Ramsey理论中的随机方法（11101086），林启忠。 3.Volterra 方程与高维分数阶扩散方程的理论与数值研究（11201077），李娴娟。
新增教育部重点项目1项：动态拓扑下WSN任务调度中多目标优化问题的算法研究，郭文忠。
实验室成员侯建锋博士获福建省自然科学基金杰青项目资助。
三、实验室不仅是高水平科学研究中心，也是高层次人才培养基地。实验室以应用数学、计算机应用技术省级重点学科，国家集成电路人才培养基地，离散数学“211工程”建设重点学科，应用数学博士点以及两个一级学科硕士点（数学、计算机科学与技术）为支撑，形成具有一定规模的离散数学高层次人才培养体系。实验室将充分利用自身的条件，围绕主攻方向，提升开放层次，促进学术交流与合作，使实验室整体研究水平达到国内领先水平，某些研究方向达到国际先进水平，为国家及福建地方建设做出突出贡献。本年度硕士研究生26名。
四、年度科研成果
实验室在各个研究问题方面开展了深入地研究工作，在课题研究中取得了一些很好的研究结果。本年度课题组研究成员在国内外重要专业刊物上发表研究SCI收录论文28篇， EI收录论文7篇。主要科研成果如下：
（1）VLSI中的图论与优化算法研究工作
1） 在大规模集成电路设计理论研究方面，课题组在开展拟定研究工作的同时, 进一步加强与集成电路设计研发和研究机构的合作，先后派出课题组成员和博士研究生共计9人次到北京华大电子了解我国目前唯一的集成电路设计工具“九天”EDA的研发进展，并针对该项研发所提出的多项实际研究问题，从理论和实际两个方面都提出了解决方案。在北京华大九天公司正在着力开发的自动化对称布线软件研发中，由于当前国内外对对称布线的系统研究非常少, 在实际布线过程中如果存在线网需要对称布线都是采用手工布线, 而且手工布线也只能解决布线层和已布线
2 网比较少的情况, 还经常出现找不到问题的解的情况。课题组得到了H-V模型下对称布线问题等价于在有效连通图中找所有引脚对应的点的一棵斯坦纳树并提出一个解决对称布线算法。本方法适合无网格且水平和垂直布线层交替出现的模型。此方法经过修改还得到一层既可以水平布线又可以垂直布线的模型下关于对称布线问题的方法。这项研究为自动化对称布线软件的开发提供了一个方法和理论保障；布线在超大规模集成电路布局面积中是一个关键性问题。Szymanski证明找一个通道布线的最小宽度是NP-困难的。课题组研究证明了通道对应的图CCG的一个最少平行团覆盖等价于一个垂直限制无圈且不添加新的空列和狗腿到网格上的二层曼哈顿模型通道布线的一个最优解。根据这个结论我们还给出了一个解决二层曼哈顿模型通道布线的一个启发式算法。为华大九天公司开发的自动化布线软件中自动化通道布线软件的开发提供了一个可行的解决方案；我们使用图论的方法对David Szeszler的2层具有Manhattan模型的通道布线的算法进行改进，并给了一个新的算法，这个算法比以前的算法所用层数更少，该项研究可用在华大九天公司正在开发的布线工具通道宽度的估计。
2） 研究并设计出器件匹配问题的一种自动匹配方法（MatchingLiu算法），该算法已用C程序实现。通过华大九天公司的评估，认为该算法快速、有效，可以帮助弥补公司新一代IC设计平台Aether的自动匹配工具的空白。
3） 研究了超大规模集成电路标准单元的布局问题。布局是超大规模集成电路物理设计的关键步骤，影响了芯片的可布线性、性能和功耗。我们研发了一个标准单元布局器，其中包含了多层全局布局和详细布局两个阶段。在全局布局阶段，我们用非线性规划方法和最优聚类技术对电路聚类，在解聚类阶段用迭代改进技术定每个单元的位置，同时缩短线长。在详细布局阶段，我们构造一个快速合法化算法把全局布局的解合法化，并用单元序消除策略改进合法化后的解。用IBM standard cell benchmark circuits和
3 Peko standard cell benchmark suite2对所构造的布局工具做测试，实验表明该布局工具可以在合理的时间内得到高质量的布局结果。
4） 研究了超大规模集成电路标准单元的布图规划问题。布图规划是超大规模集成电路物理设计的第一阶段，是NP难问题。我们构造了不可二分布图规划问题的混合模拟退火算法，该算法先用一个贪心策略生成初始的B*-tree，通过B*-tree搜索解空间，并用一个新的经验性策略平衡全局搜索和局部搜索。用MCNC benchmarks的实例对算法作测试，实验表面算法能快速找到最优解或近优解。
5） 电路划分是VLSI 物理设计自动化中的一个关键阶段，也影响了后续的电路设计，电路划分问题是NP 困难的组合优化问题。我们把该问题转化为带约束的非线性整数规划问题，同时构造了该问题的动态凸化算法。算法用改进的Fiduccia-Mattheyses (FM)算法作为非线性整数规划问题的局部搜索算法。理论分析和实验表面，通过增加一个参数的值，算法能跳出局部极小解找到更好的的解。我们用ACM/SIGDA and ISPD98 benchmarks的测试实例对算法作测试，结果表明我们的算法产生的解的质量大大优于原始的FM算法。进一步，我们把所构造的算法集成到多层划分工具MLPart中，实验表明，所得到的解的质量比MLpart提高了3-7%。此外，我们把FM 算法结合到分散搜索算法框架中，提出一种电路划分的分散搜索算法。算法利用FM 算法进行局部搜索，利用分散搜索的策略进行全局搜索。为满足分散搜索方法对初始解的质量和多样性的要求，提出采用GRASP 和聚类相结合的方法来产生初始解。实验结果表明，该算法可以求解较大规模的电路划分实例，且与基于多级框架的划分算法hMetis 相比，划分的质量有了明显的提高。
6） 研究了从集成电路中提取的max-k-cut问题，构造了该问题的一个动态凸化算法；研究了带一个连续变量的0-1背包问题，构造了快速分支定界算法；构造了非凸混合非线性整数规划问题的动
4 态凸化算法。实验验证了算法的有效性。 （2）图论与组合研究工作
在图全染色方面，证明了图的全色数等于d+1的几个充分条件，其中d表示图的最大度，其结果推广了发表在《Discrete Applied Mathematics》上的堵丁柱教授的结果。
在图无圈边染色方面，考虑了不含短圈的平面图的无圈边染色，给出了无圈边色数等于图的最大度的两个充分条件，并且给出了不含三角形或者不含四圈的平面图的无圈边色数的上界，其上界大大改进了已有结果。
在图的谱理论研究中，主要开展了关于图的代数连通度、与图与超图的划分问题相关的谱方法等问题的研究工作。得到了图的最大割新的有关无符号Laplace谱的较好上下界、具有完美匹配图的代数连通度序等多项结果。
五、学术交流
本年度来校访问并作合作研究的国内外著名学者10余人次，其中包括中科院院士、北京大学教授田刚，香港浸会大学教授朱力行，澳大利亚Newcastle大学林宇清等。
