近日，我校计算机科学与工程学院（网络空间安全学院）算法与逻辑团队在计算机与运筹交叉研究领域取得重要突破，相关论文《A Reduction-Driven Local Search for the Generalized Independent Set Problem》发表在国际顶级期刊《INFORMS Journal on Computing》（简称IJOC）。电子科技大学为论文第一完成单位，团队刘一平博士为论文第一作者，周毅副教授为通讯作者，肖鸣宇教授与法国昂热大学Jin-Kao Hao教授等共同参与指导。
IJOC是运筹学、管理科学与计算科学交叉领域最具影响力的国际学术期刊之一，由INFORMS（Institute for Operations Research and the Management Sciences）主办，长期位列UTD-24商学院顶级期刊名单。期刊重点刊载运筹优化、算法设计、人工智能、数据科学与计算决策等领域的原创性研究成果，在国际学术界享有广泛声誉。本论文是学院首篇发表于该期刊的研究成果，彰显了学院在国际前沿交叉学科领域的研究实力和学术影响力。
该论文聚焦广义独立集问题。该问题是经典最大独立集问题的重要推广形式，在保留顶点收益的同时引入边冲突代价，广泛应用于森林采伐规划、竞争设施选址、社交网络分析以及机器学习等领域。然而，随着现实网络规模的不断增长，如何高效求解超大规模广义独立集问题仍面临巨大挑战。针对这一难题，研究团队系统研究了数据规约技术在广义独立集问题中的应用（如图1所示），提出了14条具有严格最优性保证的数据规约规则，并进一步设计了一种基于数据规约驱动的局部搜索算法RLS。该算法将数据规约深度融入预处理、初始解生成和局部搜索等关键阶段，在保证求解质量的同时显著提升了计算效率。
图1：数据归约规则示例
图2：数据归约带来的规模缩减
在涵盖多个应用场景的278个基准实例上的实验结果表明，RLS算法在绝大多数测试实例上均取得了优于现有先进求解器的结果，并成功求解了边数超过2.6亿的超大规模图实例，展现出优异的求解能力和可扩展性。进一步分析表明，数据规约技术是提升算法性能的关键因素，为大规模组合优化问题的高效求解提供了新的研究思路。
电子科技大学算法与逻辑团队由欧洲科学院院士、新西兰皇家学会院士Bakh Khoussainov教授和肖鸣宇教授共同组建，现有许超教授、Toru Takisaka教授、周毅副教授、郝东副教授等多位骨干成员。团队长期从事算法设计与分析、组合优化、图论与图算法、算法工程、人工智能与运筹优化等方向的研究，在理论研究与实际应用之间形成了鲜明特色。近年来，团队在LICS、CAV、SODA、WINE, EC, IANDC, Math. Program., AIJ等国际顶级学术会议以及国际高水平期刊上持续发表重要成果，研究实力和学术影响力不断提升。此次IJOC论文的录用，进一步彰显了团队在计算与运筹前沿领域的国际竞争力。
未来，算法与逻辑团队将继续聚焦组合优化、算法工程、运筹管理与人工智能交叉方向的基础理论与关键技术研究，深化国际合作，推动原创性成果产出，为解决复杂大规模优化问题贡献更多“成电智慧”。
论文信息：
--------
Title:
A Reduction-Driven Local Search for the Generalized Independent Set Problem
Authors:
Yiping Liu, Yi Zhou*, Zhenxiang Xu, Mingyu Xiao, and Jin-Kao Hao
论文链接：https://pubsonline.informs.org/doi/10.1287/ijoc.2025.1203
