知行融创论坛第三期活动成功举办

基础软件与系统重点实验室党支部于 2025 年 6月 25日成功举办了“知行融创”论坛第三期活动。本次活动聚焦基础软件与系统领域的核心算法与理论创新，四位同志带来了精彩的前沿研究分享，以下是报告的主要内容。

林鹏：基于动态任务分解的并行混合整数规划求解
混合整数规划（MIP）是运筹学的基础模型。尽管序列MIP求解器在技术和启发式方法上取得了显著进步，但计算资源的飞速发展为并行求解带来了广阔前景。林鹏同志提出了一种新颖的并行MIP求解框架，采用分治范式下的动态任务分解策略。该框架融合了难度评估启发式算法来识别高难度任务，以及奖励衰减机制来优化任务分解决策。该框架成功应用于SCIP和HiGHS两大前沿开源MIP求解器，构建了高效的并行求解器。在完整MIPLIB基准集上的大规模实验（使用高达128核）表明，该框架相较现代分治并行求解器取得了显著性能提升，并为16个公开的MIPLIB实例建立了新的最佳已知解。

刘程华：量子加速随机生成树采样
刘程华同志提出了一种量子算法，用于从加权图中采样随机生成树，时间复杂度为 \widetilde O(√mn)（n和m分别为顶点和边数）。该算法对稠密图具有亚线性运行时间，相较于已知最佳经典算法实现了量子加速。其核心是巧妙结合了基于“大步”随机游走以减少混合时间的经典方法，以及量子图稀疏化、Hamoudi多态制备的无放回采样变种等量子算法技术。研究同时建立了匹配的下界，证明了算法在多项式对数因子内的最优性。这些成果凸显了量子计算在加速基础图采样问题上的潜力。

郑加毅：从奇元签名到Holant二分性
Holant是计数复杂性领域的重要框架。针对布尔域上复值Holant的复杂性分类，这一悬而未决超过十五年的挑战，郑加毅同志取得了重要进展。他证明了当存在非平凡的奇元签名时，布尔域上复值Holant存在复杂性二分性。该二分性基于#EO问题的二分性，因而也是一个FP^NP vs. #P的二分性，即每个问题要么属于FP^NP，要么是#P-难的。此外，他还建立了布尔域上复值Holant的广义分解引理版本，表明每个签名要么可以与其张量积中的其他签名导出，要么问题本身属于FP^NP。该引理是构建复值Holant约简的有力工具，也是文章核心二分性证明的关键技术。

吴陶然：基于集合边界分析的可达性计算
吴陶然同志介绍了基于集合边界分析的可达性分析工具包PyBDR和BdryReach。这些工具核心思想是针对形式化验证、控制器综合、状态估计等领域广泛采用的集合传播技术，通过分析初始集合的边界来缓解计算过程中的包裹效应（wrapping effect），从而在不显著增加计算成本的前提下提升可达性分析算法的性能。对比研究展示了它们在处理具有大初始集或长时程验证任务方面的优势。

本期“知行融创”论坛围绕基础软件与系统领域的关键算法理论与技术突破，展示了实验室党员在并行计算、量子算法、计算复杂性理论、形式化方法等前沿方向的创新成果。论坛持续为党员同志搭建了高水平的学术交流与思想碰撞平台，有效促进了不同研究方向间的交叉融合，生动实践了党建与科研业务的深度融合，激励党员在服务国家重大战略需求的科研一线攻坚克难、勇攀高峰。